0

我有点卡在这个涉及返回字符串数组中同构对的数量的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;  
  }  
}

我真的很感激你能给我关于这段代码的任何反馈。

谢谢，朱奈德

4

2 回答 2

3

它给出错误答案的原因可能来自您计算字母数，而不是查看它们在两个单词中的位置。我想到的第一个解决方案是创建一个新数组，在其中将字母转换为每个单词第一次出现该字母的索引。例如：“abcd”是“0123”，“abca”是“0120”，“fhjf”也是“0120”。然后，您可以简单地比较结果。我希望这有帮助...

于 2014-01-29T21:04:27.283 回答
0 
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;
}
于 2014-01-29T20:08:12.043 回答