从字典中找到单词变位词的最佳算法

  • Z时代
  • 2024-01-10
  • 分类：问答

我遇到这样的问题

我有一个列表，它是包含数百万个单词的词典，并且输入类似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();
  }
}

以上是 从字典中找到单词变位词的最佳算法 的全部内容， 来源链接： utcz.com/qa/411486.html

回到顶部