Java Isomorphic Code

Question

I am kind of stuck on this java problem involving returning the number of isomorphic pairs in an array of Strings. The code I have written keeps returning incorrect number of isomorphic word pairs.

The definition of isomorphic words is given as follows: Two words are called isomorphic if the letters in one word can be remapped to get the second word. Remapping a letter means replacing all occurrences of it with another letter. The ordering of the letters remains unchanged. No two letters may map to the same letter, but a letter may map to itself. For example, the words "abca" and "zbxz" are isomorphic because we can map 'a' to 'z', 'b' to 'b' and 'c' to 'x'. I am not inlcuding the getMap method which I call in the function. The getMap method take any string as input, and returns a map where the keys are the letters in the string, and the corresponding values are the number of times the letter appears in the string.

  public class IsomorphicWords {
  public int countPairs(String[] words) {
     Set <String> pairs = new HashSet<String>();
     for (String word:words){
         Map noOfOccurencesOfEachLetter= getMap(word);
         ArrayList<Integer> valuesFromFirstWord = new ArrayList<Integer>(noOfOccurencesOfEachLetter.values());
         Collections.sort(valuesFromFirstWord);
         java.util.List<String> list = new ArrayList<String>(Arrays.asList(words));
         list.remove(word);
         String[] oneLessWord = list.toArray(new String[words.length-1]);
         for(String secondWord:oneLessWord){
             Map secondNoOfOccurencesOfEachLetter = getMap(secondWord);
             ArrayList<Integer> valuesFromSecondWord = new ArrayList<Integer>(secondNoOfOccurencesOfEachLetter.values());
             Collections.sort(valuesFromSecondWord);
             if (valuesFromFirstWord.equals(valuesFromSecondWord)){
                pairs.add(""+word+","+secondWord+"");
             }
             else{
                 continue;
             }
         }


     }
 return pairs.size()/2;
 public Map getMap(String word){
      HashMap<String,Integer> noOfOccurencesOfEachLetter= new HashMap<String,Integer>();
      for (int i=0;i<word.length();i++){
          char letter = word.charAt(i);
          String letterInDictionary= Character.toString(letter);
          if (noOfOccurencesOfEachLetter.containsKey(letterInDictionary)==true){
                int count= noOfOccurencesOfEachLetter.get(letterInDictionary);
                noOfOccurencesOfEachLetter.put(letterInDictionary, count+1);
            }
           else{
                noOfOccurencesOfEachLetter.put(letterInDictionary, 1); 
            }
      }
      return noOfOccurencesOfEachLetter;  
  }  
}

I'd really appreciate any feedback you can give me on this code.

Thanks, Junaid

Answer 1

The reason why it gives the incorrect answer probably comes from you take the letter count, and don't look at the position that they have in both words. The first solution that comes up in me, is to create a new array in which you translate the letters to the index of the first occurrence of this letter for each word. For example: "abcd" would be "0123", "abca" would be "0120" and "fhjf" would be "0120" as well. Then you can simply compare the results. I hope this helps...

Answer 2

public int countPairs(String[] words) {
    int isomorphicPairs = 0;
    for (int i = 0; i < words.length; i++) {
        for (int j = i+1; j < words.length; j++) {
            if (words[i].length() == words[j].length()) {
                String tmp = new String(words[j]);
                for (int k = 0; k < tmp.length(); k++)
                    tmp = tmp.replaceAll("" + tmp.charAt(k), "" + words[i].charAt(k));
                if (words[i].equals(tmp)) isomorphicPairs++;
            }
        }
    }
    return isomorphicPairs;
}