如何让变位词程序代码更快？（Java）

Question

我是一名经验不太丰富的程序员。我写了一个词语重组程序，唯一的问题是速度不够快。有人告诉我嵌套的for循环是问题所在，但我无法想出如何解决它（set1是包含所有单词的HashSet，map是LinkedHashMap<String, String>，anagram是TreeMap<String, TreeSet<String>>）：

for (String element : set1) {
    char[] woord = element.toCharArray(); //alfabetical order of each word
    Arrays.sort(woord);
    String chartostring = new String(woord);
    map.put(element, chartostring); // add each word with its sorted letters
    TreeSet<String> order_words = new TreeSet<String>(); //creating list of anagrams
    for (String o : map.keySet()) { //for each word
        if (map.get(o).equals(chartostring)) { //check if there is a value in map which is equal to the sorted letters
            order_words.add(o); //add word to list of anagrams
            if (order_words.size() > 1) { //we want anagrams so only print if there are atleast 2 words
                anagram.put(chartostring, order_words);
            }
        }
    }
}

有人可以帮我吗？非常感谢。

- maria

Answer 1

嵌套循环实际上是很慢的，因为你像迭代列表一样迭代一个映射。如果你能用哈希表快速查找来替换嵌套循环不是很好吗？不幸的是，当你处理Map<String,String>时，这不是一个选项，因为多个单词将具有相同的排序表示。这就是为什么你要建立一个从单词到其排序表示的映射，而不是反过来。

然而，这意味着你可以建立一个从排序表示到单词列表的映射：

Map<String,List<String>> sortedRepToWords

您可以在开始匹配之前，使用单个循环来构建此映射。有了这个列表映射，您可以消除嵌套循环，取而代之的是从sortedRepToWords中查找整个列表。

- Sergey Kalinichenko

---

谢谢您的评论，我会尝试的。我是一个初学者，所以并不知道所有的选项。 - maria

Answer 2

介绍Java 8...

import java.util.stream.Stream;
import static java.util.stream.Collectors.*;

Map<String, List<String>> tmp = set1.parallelStream() // Possibly using multiple cores...
    .collect(groupingBy(s-> sortMe(s))); // One liner!

List<List<String>> result = tmp.values().stream()
    .filter(l -> l.size() > 1)  // At least 2 anagrams
    .collect(toList());

System.out.println(tmp);
System.out.println(result);

//...//

// If you really want to use Java 8 for sorting a String...
private String sortMe(String input) {
    return Stream.of(input.split("")).sorted().collect(joining());
}

- Marsellus Wallace

Answer 3

如果您使用HashSet，可以按照1的顺序（单循环）完成此操作。

Set<char[]> dict_set = new HashSet<char[]>();
Set<char[]> anag_set = new HashSet<char[]>();

for (String element : set1) {

 // Sort the characters in string.
 char[] woord= element.toCharArray();
 Arrays.sort(woord);

 //if already encountered add as a known anagram
 //else add the sorted charset to the dictionary.

 if (dict_set.contains(woord)) anag_set.add(woord)
 else dict_set.add(word);

 return anag_set;
}

如果您需要所有的变位词及其排序形式，可以使用一个排序后的映射表和一个包含所有相关变位词的列表。PS：这只是伪代码。

- Rupertt Wind

---

由于它是哈希集，查找非常快，您可以省去for循环。 - Rupertt Wind

Answer 4

我不知道在你的情况下是否更好，但当我需要一个map的key和value时，我使用entrySet。这样可以避免调用get方法，节省了一部分时间...

https://dev59.com/3G865IYBdhLWcg3wU8-I#3870210

for (String element : set1) {
    char[] woord = element.toCharArray(); //alfabetical order of each word
    Arrays.sort(woord);
    String chartostring = new String(woord);
    map.put(element, chartostring); // add each word with its sorted letters
    TreeSet<String> order_words = new TreeSet<String>(); //creating list of anagrams
    for (Entry o : map.entrySet()) { //for each word
        if (o.getValue().equals(chartostring)) { //check if there is a value in map which is equal to the sorted letters
            order_words.add(o.getKey()); //add word to list of anagrams
            if(order_words.size()>1){ //we want anagrams so only print if there are atleast 2 words
                  anagram.put(chartostring, order_words); 
              }
        }
    }
}

如果这还不够的话，我认为你应该用另一种逻辑重写你的代码，并尝试实现dasblinkenlight的答案。

- Dams

---

我应该将这个放在内部循环中替换还是放在外部？ - maria

我不明白你的问题，我已经为这个例子调整了你的代码...尝试替换或将其放在外面。 - Dams

哦，我看懂了。谢谢！我会尝试一下，看看这是否能解决问题，因为我仍然有一个嵌套的for循环。 - maria

Answer 5

// Importing the Arrays class that will help us manipulate arrays.
import java.util.Arrays;

public class AnagramTest {

  private static boolean isAnagram(String str1 , String str2){
    // Converting both strings to char arrays as strings do not have direct
    // sorting method in java.
    char [] leftArray = ( str1.trim().toLowerCase()).toCharArray();
    char [] rightArray = ( str2.trim().toLowerCase()).toCharArray();
    Arrays.parallelSort(leftArray);
    Arrays.parallelSort(rightArray);

    if(leftArray.length != rightArray.length){
      return false;
    }
    // Both char arrays have the same number of characters
    for(int i = 0; i < leftArray.length; i++){
      if(leftArray[i] != rightArray[i]){
        return false;  
      }
    }
    // We only get to this stage if all the elements pass the if test
    return true;
  }

  public static void main(String [] args){
    String a = "integral"; // initializing first string
    String b = "Triangle"; // initializing second string
    System.out.println(isAnagram(a,b));     
  }         
}

- Jeancy Tshibemba Mukendi

---

这并没有真正解决在单词列表中查找变位词的问题。它只是比较两个字符串是否是变位词。 - Scratte