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