从字典中查找单词字谜的最佳算法[关闭]

我遇到了这样的问题

我有一个列表，它是包含数百万个单词的字典，我输入一个像 OSPT 这样的单词，只有 2 个单词可以组成 STOP 和 POST 。 我想以优化的方式找出字典中匹配的所有字谜词。

我解决了什么。

我给出了下面的解决方案。我将获取该单词并对其进行排列，然后检查该单词是否存在于字典中。但这不是 n*n 优化的。有什么方法可以解决这个问题

您可以按字母顺序对每个单词中的字符进行排序，以形成映射中的键，其值是该键的单词列表。

当给你一个单词来查找字谜词时，你可以按字母顺序对该单词中的字符进行排序，并在地图中进行查找。

从您的示例中添加单词 POOL，您将得到：

LOOP -> [LOOP, POOL, POLO]
OPST -> [STOP, POST]

Java 代码类似于：

public class AnagramGenerator
{
  private Map<String, Collection<String>> indexedDictionary;

  public AnagramGenerator(List<String> dictionary)
  {
    this.indexedDictionary = index(dictionary);
  }

  public Collection<String> getAnagrams(String word)
  {
    return indexedDictionary.get(sort(word));
  }


  private Map<String, Collection<String>> index(List<String> dictionary)
  {
    MultiMap<String, String> indexedDictionary = HashMultimap.create();

    for (String word : dictionary)
    {
      indexDictionary.put(sort(word), word);
    }

    return indexedDictionary.asMap();
  }

  private String sort(String word) 
  {
    List<Character> sortedCharacters= Arrays.asList(word.toCharArray());
    Collections.sort(sortedCharacters);

    StringBuilder builder = new StringBuilder();
    for (Character character : sortedCharacters)
    {
      builder.append(character);
    }

    return builder.toString();
  }
}