Java character array prints the index

Question

char_array[] is "x, a, x, c, x, b, x, a, x, x ,b ,x ,x, x, x"

key_array[] is "a, b, c"

expected return array: "1, 5, 3"

The goal is to print the index of the char_array that matches with key_array. For example, in this case the program has to print "1, 5, 3". It only counts the first index it matches.

Another example would be that

char_array[] is "q, h, e, h, w, e, r, t, l, y, l, l, o"

key_array[] is "h, e, l, l, o"

expected return array: "1, 2, 8, 10, 12"

What I have tried so far is

int index = 0;
for(int i = 0; i < key_array.length; i++)
{
    isFound = false;
    for(int k = index + 1; k < char_array.length && isFound == false; k++) 
    {
        if(char_array[i] == key_array[k])
        {
            index = k;
            num[j] = index;
            isFound = true;
        }
    }
}

This way, my second example which deals with "hello" works but my first example which deals with "abc" doesn't work.

I started my k with index+1, but I guess I will have to change this from 0 to char_array.length..

Can someone help me with this logic please

Answer 1

I think this will do the job ( O(n) ) :

char[] char_array = {'q', 'h', 'e', 'h', 'w', 'e', 'r', 't', 'l', 'y', 'l', 'l', 'o'};
char[] key_array = {'h', 'e', 'l', 'l', 'o'};

Map<Character, Queue<Integer>> charPossitions = new HashMap<Character, Queue<Integer>>();
for(int i = 0; i < char_array.length; i++){
    if(charPossitions.get(char_array[i]) == null){           
       Queue<Integer> possitionsQueue=new LinkedList<Integer>();
       possitionsQueue.add(i);
       charPossitions.put(char_array[i], possitionsQueue);
    }else { 
       charPossitions.get(char_array[i]).add(i);
    }                                           
}
for(char key : key_array){
    System.out.println(key + "/" + charPossitions.get(key).poll());
}

Answer 2

Hello this shoul do the trick!

public class Main
{

  private static final char[] liste1 = {'x', 'a', 'x', 'c', 'x', 'b', 'x', 'a', 'x', 'x' ,'b' ,'x' ,'x', 'x', 'x'};
  private static final char[] liste2 = {'q', 'h', 'e', 'h', 'w', 'e', 'r', 't', 'l', 'y', 'l', 'l', 'o'};
  private static final char[] key1 = {'a', 'b', 'c'};
  private static final char[] key2 = {'h', 'e', 'l', 'l', 'o'};


  private static void lookupIndexOfChar(char c, char[] list, List<Integer> result){
    for(int i = 0; i < list.length; i++){
      if(list[i] == c){
        if(notInResult(i, result)){
          result.add(i);
          break;
        }
      }
    }
  }

  private static boolean notInResult(int i, List<Integer> result)
  {
    return !(result == null || result.contains(i));
  }

  public static void main(String[] args){
    List<Integer> result = new ArrayList<Integer>();
    for (char c : key1)
    {
      lookupIndexOfChar(c, liste1, result);
    }
    for (Integer integer : result)
    {
      System.out.print(integer);
    }
    System.out.println(" ");
    result.clear();
    for (char c : key2)
    {
      lookupIndexOfChar(c, liste2, result);
    }
    for (Integer integer : result)
    {
      System.out.print(integer);
    }
  }

}

Answer 3

This only works for the second example, since the chars occur in order.

However you need to decide the index to start the search based on whether you've seached the string for this char before (start after the char found).

E.g.

for (int i = 0; i < key_array.length; i++) {
     char c = key_array[i];
     int previousIndex;

     // go back and find the last index with a matching char
     for (previousIndex = i-1; previousIndex >= 0 && key_array[previousIndex] != c; previousIndex--) {}

     if (previousIndex >= 0 && num[previousIndex] == -1) {
          // last key not found => no further matches available
          num[i] = -1;
     } else {
          // find occurence of char after last match
          num[i] = -1;
          for (int j = (previousIndex >= 0 ? num[previousIndex] + 1 : 0); j < char_array.length; j++) {
               if (char_array[j] == c) {
                    num[i] = j;
                    break;
               }
          }
     }
}

---

Alternatively use a Map to store the indices by char and use this to retrieve the indices efficiently:

// find list of indices by char
Map<Character, ?> map = IntStream.range(0, char_array.length).boxed().collect(Collectors.groupingBy(i -> char_array[i]));

for (Map.Entry e : map.entrySet()) {
    // replace values with iterator over index lists
    e.setValue(((List)e.getValue()).iterator());
}

for (int i = 0; i < key_array.length; i++) {
    Iterator<Integer> iterator = (Iterator<Integer>) map.get(key_array[i]);
    num[i] = (iterator == null || !iterator.hasNext() ? -1 : iterator.next());
}

Answer 4

Try this;

for(int i=0;i<key_array.length;i++)
{
    int pos=new String(char_array).indexOf(key_array[i]);

    char_array[pos]='0'                          //considering there is no numeric character in char_array  

    collection.push(pos);                        //collection is a java Collection framework's object
}

Answer 5

Seems to do the trick

static int[] foo(char[] char_array, char[] key_array) {
    // copy the original so we can modify to avoid repeats
    char[] copy = new char[char_array.length];
    System.arraycopy(char_array, 0, copy, 0, char_array.length);
    int[] result = new int[key_array.length];
    boolean found = true;
    for(int i = 0; found && i < key_array.length; i++) {
        found = false;
        for(int j = 0; j < copy.length; j++) {
            if (copy[j] == key_array[i]) {
                copy[j] = 0;
                result[i] = j;
                found = true;
                break;
            }
        }
    }
    if (found) {
        return result;
    }
    return null;
}

public static void main(String[] args) {
    System.out.println(Arrays.toString(foo("xaxcxbxaxxbxxxx".toCharArray(), "abc".toCharArray())));
    System.out.println(Arrays.toString(foo("qhehwertlyllo".toCharArray(), "hello".toCharArray())));
}