如何解決排序的anagrams

Question

我有一個單詞列表如下。

pear amleth dormitory tinsel dirty room hamlet listen silnet

我想找出所有字謎並按照順序列出。如果沒有發現任何東西，只需輸出該字。所以在上述情況下，輸出應該是。

amleth,hamlet dirty room,dormitory listen,silnet,tinsel pear

下面是我爲的書面Java代碼。

public class Anagram { 

    private boolean isAnagram(String s1, String s2) { 

     if (s1.length() != s2.length()) { 
      return false; 
     } 
     Map<Character, Integer> anagramMap = new HashMap<>(); 
     for (char ch = 'a'; ch <= 'z'; ++ch) 
      anagramMap.put(ch, 0); 
     for(int i=0; i<s1.length(); i++){ 
      anagramMap.put(s1.charAt(i), anagramMap.get(s1.charAt(i))+1); 
     } 
     for(int j=0; j<s2.length(); j++) { 
      if (anagramMap.get(s2.charAt(j)) != 0) { 
       anagramMap.put(s2.charAt(j), anagramMap.get(s2.charAt(j)) - 1); 
      } 
     } 
     for(int value : anagramMap.values()) { 
      if (value != 0) { 
       return false; 
      } 
     } 
     return true; 
    } 
    private void solveChallenge(List<String> words) { 
     for(int i=0 ;i<(words.size()-1); i++) { 
      Set<String> result = new TreeSet<>(); 
      for(int j=(i+1); j< words.size(); j++) { 
       if (isAnagram(words.get(i), words.get(j))){ 
        result.add(words.get(i) + " " + words.get(j)); 
        System.out.println(result); 
        words.remove(j); 
       } 
      } 
     } 
    } 

    public static void main(String[] args) { 
     Anagram anagram = new Anagram(); 
     List<String> words = new ArrayList<>(); 
     BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); 
     try { 
      String line = reader.readLine(); 
      Integer numTestCases = Integer.parseInt(line); 
      while (--numTestCases >= 0){ 
       words.add(reader.readLine().replaceAll("\\s+","").toLowerCase()); 
      } 
      System.out.println(words); 
      new Anagram().solveChallenge(words); 
     } catch (IOException e) { 
      e.printStackTrace(); 
     } 

    } 
} 

但它沒有列出所需的輸出。我得到的輸出是 [amleth hamlet] [dormitory dirtyroom] [tinsel lisetn]

有人可以告訴我這裏有什麼問題嗎？

Answer 1

您已在代碼一些錯誤。首先，您需要更改存儲集合中字符的邏輯。你在這裏存儲pair，而你應該在這裏存儲所有的字符。因此，您可以使用StringBuilder來將anagrams存儲在single通過中，並且在迭代之後，您可以將其添加到該集中。

另一個錯誤是在這個循環：

for(int j=(i+1); j< words.size(); j++) { 
    if (isAnagram(words.get(i), words.get(j))){ 
     result.add(words.get(i) + " " + words.get(j)); 
     System.out.println(result); 
     words.remove(j); 
    } 
} 

在這裏，您是從列表中刪除的element然後遞增j因此，有可能剝離後，所有的元素得到由1地方轉移提前所以如果未來元素是anagram那麼你會錯過它，因爲你正在增加j。最後一個錯誤是您需要檢查words列表的所有元素。因爲有可能最後一個元素不是與任何其他元素的字母組合，那麼就需要分開進行。

因此，請在solveChallenge()功能幾點變化：

private void solveChallenge(List<String> words) { 
    for(int i=0 ;i<(words.size()); i++) { 
     Set<String> result = new TreeSet<>(); 
     StringBuilder resultant_string = new StringBuilder(words.get(i)); //To store the all anagrams 
     for(int j=(i+1); j< words.size(); j++) { 
      if (isAnagram(words.get(i), words.get(j))){ 
       resultant_string.append(" ").append(words.get(j)); 
       words.remove(j); 
       j--;  //If anagram found, stay on the current element 
      } 
     } 
     result.add(resultant_string.toString()); 
     System.out.println(resultant_string); 
    } 
} 

根據自己的需要，我曾在節目中的一些變化。

代碼：

class Anagram { 

    private boolean isAnagram(String s1, String s2) { 
     s1=s1.replaceAll("\\s+",""); 
     s2=s2.replaceAll("\\s+",""); 
     if (s1.length() != s2.length()) { 
      return false; 
     } 
     Map<Character, Integer> anagramMap = new HashMap<>(); 
     for (char ch = 'a'; ch <= 'z'; ++ch) 
      anagramMap.put(ch, 0); 
     for(int i=0; i<s1.length(); i++){ 
      anagramMap.put(s1.charAt(i), anagramMap.get(s1.charAt(i))+1); 
     } 
     for(int j=0; j<s2.length(); j++) { 
      if (anagramMap.get(s2.charAt(j)) != 0) { 
       anagramMap.put(s2.charAt(j), anagramMap.get(s2.charAt(j)) - 1); 
      } 
     } 
     for(int value : anagramMap.values()) { 
      if (value != 0) { 
       return false; 
      } 
     } 
     return true; 
    } 
    private void solveChallenge(List<String> words) { 
     List<String> result = new ArrayList<>(); 
     for(int i=0 ;i<(words.size()); i++) { 
      List<String> resultant_strings=new ArrayList<>(); 
      resultant_strings.add(words.get(i)); 

      for(int j=(i+1); j< words.size(); j++) { 
       if (isAnagram(words.get(i), words.get(j))){ 
        resultant_strings.add(words.get(j)); 
        words.remove(j); 
        j--; 
       } 
      } 
      Collections.sort(resultant_strings); 
      String resultant_string=resultant_strings.toString(); 
      result.add(resultant_string); 
     } 
     Collections.sort(result); 
     System.out.println(result); 
    } 

    public static void main(String[] args) { 
     Anagram anagram = new Anagram(); 
     List<String> words = new ArrayList<>(); 
     BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); 
     try { 
      String line = reader.readLine(); 
      Integer numTestCases = Integer.parseInt(line); 
      while (--numTestCases >= 0){ 
       words.add(reader.readLine().toLowerCase()); 
      } 
      System.out.println(words); 
      new Anagram().solveChallenge(words); 
     } catch (IOException e) { 
      e.printStackTrace(); 
     } 

    } 
} 

打印結果：

[[amleth, hamlet], [dirty room, dormitory], [listen, silnet, tinsel], [pear]] 

Answer 2

這將解決你的問題

public class Anagram { 

private boolean isAnagram(String s1, String s2) { 

    if (s1.length() != s2.length()) { 
     return false; 
    } 
    Map<Character, Integer> anagramMap = new HashMap<>(); 
    for (char ch = 'a'; ch <= 'z'; ++ch) 
     anagramMap.put(ch, 0); 
    for(int i=0; i<s1.length(); i++){ 
     anagramMap.put(s1.charAt(i), anagramMap.get(s1.charAt(i))+1); 
    } 
    for(int j=0; j<s2.length(); j++) { 
     if (anagramMap.get(s2.charAt(j)) != 0) { 
      anagramMap.put(s2.charAt(j), anagramMap.get(s2.charAt(j)) - 1); 
     } 
    } 
    for(int value : anagramMap.values()) { 
     if (value != 0) { 
      return false; 
     } 
    } 
    return true; 
} 
private void solveChallenge(List<String> words) { 
    for(int i=0 ;i<(words.size()-1); i++) { 
     Set<String> result = new TreeSet<>(); 
     int j = i+1; 
     while(j < words.size()) { 
      if (isAnagram(words.get(i), words.get(j))){ 
       result.add(words.get(i) + " " + words.get(j)); 
       System.out.println(result); 
       words.remove(j); 
      } else { 
      j++; 
      } 
     } 
    } 
} 

public static void main(String[] args) { 
    Anagram anagram = new Anagram(); 
    List<String> words = new ArrayList<>(); 
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); 
    try { 
     String line = reader.readLine(); 
     Integer numTestCases = Integer.parseInt(line); 
     while (--numTestCases >= 0){ 
      words.add(reader.readLine().replaceAll("\\s+","").toLowerCase()); 
     } 
     System.out.println(words); 
     new Anagram().solveChallenge(words); 
    } catch (IOException e) { 
     e.printStackTrace(); 
    } 

} 
} 

只有當你不刪除任何元素，因爲remove（）方法所導致的問題，您應該增加學家現在

我會建議你應該使用HashMap的<字符串，ArrayList的<字符串>>這樣的數據結構。希望這有助於:)

Answer 3

這是我怎麼會去一下：

• 每個字，創建一個Map<Character, Integer>包含單詞的字符（不包括空格）和occurence的數量 - 你有已經做了類似的事情
• 然後將它們存儲在Map<Map<Character, Integer>, List<String>>中，其中關鍵是出現的映射，並且值是匹配的所有單詞的列表（anagrams）。 Map::equals會自動爲您做比較。

示例實現看起來是這樣的：

String[] words = ("pear", "amleth", ... }' 
Map<Map<Integer, Long>, List<String>> characters = new HashMap<>(); 
for (String word : words) { 
    //here I'm using a stream, but you can build the occurences map manually 
    Map<Integer, Long> occurences = word.replaceAll("\\s+", "") //remove spaces 
        .chars().boxed() 
        .collect(Collectors.groupingBy(i -> i, Collectors.counting())); 

    if (characters.containsKey(occurences)) { //anagram found ! 
    characters.get(occurences).add(word); //add the word to the list 
    } else { //no anagram found, create the list, with only one item 
    List<String> list = new ArrayList<>(); 
    list.add(word); 
    characters.put(occurences, list); 
    } 
} 

//you may want to sort the lists here 

characters.values().forEach(System.out::println);