我得到了一个问题，这样的事情

I was given a problem something like this

我有一个List它是一个包含数百万字的字典，我定的输入像OSPT一个字onlt 2字可以形成STOP和POST .. 我想找出所有字谜词语的dictonary以优化的方式匹配。

I have a List which is dictionary containing millions of words and I am given input a word like OSPT onlt 2 words can be formed STOP and POST.. I want to find out all anagram words matching in dictonary in optimized way.

我解决了。

我给了下面solution.I将取词和重排，并检查该单词存在于字典或not.But这是N * N不optimized.Is有什么办法可以解决这个问题。

I gave below solution.I will take the word and permute it and check the word exist in dictionary or not.But this is n*n not optimized.Is there any way to solve this

推荐答案

您在每个字的字符的字母顺序排序，形成一个映射，其值是字是关键的列表项。

You sort the characters in each word alphabetically to form key in a map whose values are the lists of words for that key.

当你给一个词，找到字谜的，你按字母顺序在单词中的字符进行排序，并做了查找在地图上。

When you're given a word to find the anagrams for, you sort the characters in that word alphabetically and do a lookup in the map.

这是你的榜样，并添加文字POOL，你会得到：

From your example and adding the word POOL, you'd get:

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

Java的code会是这样的：

The Java code would be something like:

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