Counting the number of common chars in a string and a vector of strings

Question

My problem is how to count but not count the same character twice. Like comparing 'aba' to 'are' should give 1 as result since it has only one char in common.

This is where I got so far:

public int sameChars (Vector<String> otherStrs){
    int result = 0;
    String original = "aba";
    for (int h= 0; h< otherStrs.size(); h++) {
        String targetStr = otherStrs.get(h);
        for (int i=0; i< original.length(); i++) {
            char aux = original.charAt(i);
            for (int j=0; j< Math.min(original.length(), targetStr.length()); j++) {
                char targetAux = targetStr.charAt(j);
                if (aux == targetAux) {
                    result++;
                    break;
                }
            }
        }
    }
    return result;
}

Ideas are welcome, thanks.

Answer 1

You can create a hash of character count from the original string. Then for each target string, check if it has a char that has a non-zero value in your hash. This will prevent scanning your original string more than once.

Pseudocode:

For each char c in original string {
  hash[c]++
}
For each target string str {
  For each char c_ in str {
    if hash[c_] > 0 {
      result++;
    }
  }
}

Answer 2

This smells like homework, so here's the just the basic idea: You need to keep track of the distinct characters you've already counted as being in both places. A Set might be a good way to do this. Before incrementing your counter, check to see if the character you're looking at is already in that Set.

Answer 3

I am not sure to understand your requirement: do you want to count the number of times the distinct characters found in the reference string original, here "aba" thus 'a' and 'b', are found in a set of strings stored in the Vector otherStrs?

If that's the case, I would advise first to reduce the original string to distinct characters (looking for and removing duplicates, or using a Map). Then loop over the strings in the Vector and do the same for each string (removing duplicates or using a Map) before incrementing your counter each time a character is found in common.

Just out of curiosity, what is the end goal of this computation?

Answer 4

Here's my implementation:

public static int commonChars(String s1, String s2) {
 if (s1 == null || s1.isEmpty())
  throw new IllegalArgumentException("Empty s1");
 if (s2 == null || s2.isEmpty())
  throw new IllegalArgumentException("Empty s2");

 char[] a1 = s1.toCharArray();
 char[] a2 = s2.toCharArray();

 Arrays.sort(a1);
 a1 = removeDups(a1);
 Arrays.sort(a2);
 a2 = removeDups(a2);

 int count = 0;

 for (int i = 0, j = 0; i < a1.length && j < a2.length;) {
  if (a1[i] == a2[j]) {
   i++;
   j++;
   count++;
  }
  else if (a1[i] > a2[j]) 
   j++;
  else
   i++;
 }

 return count;
}

public static char[] removeDups(char[] array) {
 char[] aux = new char[array.length];
 int c = 1;
 aux[0] = array[0];
 for (int i = 1 ; i < array.length; i++) {
  if (array[i] != array[i-1])
   aux[c++] = array[i];
 }
 return Arrays.copyOf(aux, c);
}