Java Isomorphic Code

Question

Я как бы застрял в этой java-проблеме, связанной с возвратом числа изоморфных пар в массив строк. Код, который я написал, продолжает возвращать неправильное число изоморфных пар слов.

Определение изоморфных слов задается следующим образом: Два слова называются изоморфными, если буквы в одном слове можно перегруппировать, чтобы получить второе слово. Перемещение буквы означает замену всех вхождений в нее другой буквой. Порядок букв остается неизменным. Никакие две буквы не могут сопоставляться с одним и тем же письмом, но буква может отображаться сама по себе. Например, слова «abca» и «zbxz» изоморфны, потому что мы можем сопоставить «a» с «z», «b» и «b» и «c» в «x». Я не использую метод getMap, который я вызываю в функции. Метод getMap принимает любую строку в качестве входных данных и возвращает карту, где ключи являются буквами в строке, а соответствующие значения - это количество раз, когда буква появляется в строке.

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; 
    } 
} 

Я бы очень признателен за любые отзывы, которые вы можете дать мне по этому коду.

Спасибо, Junaid

Answer 1

Причина, почему это дает неправильный ответ, вероятно, происходит от вас взять количество письмо, и не смотрите на той позиции, что у них есть в обоих словах. Первое решение, которое возникает во мне, заключается в создании нового массива, в котором вы переводите буквы в индекс первого вхождения этой буквы для каждого слова. Например: «abcd» будет «0123», «abca» будет «0120», а «fhjf» будет «0120». Затем вы можете просто сравнить результаты. Я надеюсь, что это поможет ...

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; 
}