从dictonary中找到单词的最佳算法
我遇到了类似这样的问题
我有一个列表，其中包含数百万个单词的字典，我输入一个像OSPT onlt这样的单词可以形成STOP和POST ..我想找出所有在dictonary中匹配的字谜单词以优化的方式。
我解决了什么。
我给出了下面的解决方案。我会接受这个词并置换它并检查字典中存在的单词与否。但这是n * n未优化。有什么方法可以解决这个问题
您按字母顺序对每个单词中的字符进行排序，以在地图中形成键，其值是该键的单词列表。
当您给出一个单词来查找字谜时，您会按字母顺序对该单词中的字符进行排序并在地图中进行查找。
从您的示例并添加单词POOL，您将获得：
LOOP -> [LOOP, POOL, POLO] OPST -> [STOP, POST] Java代码将类似于：
public class AnagramGenerator { private Map> indexedDictionary; public AnagramGenerator(List dictionary) { this.indexedDictionary = index(dictionary); } public Collection getAnagrams(String word) { return indexedDictionary.get(sort(word)); } private Map> index(List dictionary) { MultiMap indexedDictionary = HashMultimap.create(); for (String word : dictionary) { indexDictionary.put(sort(word), word); } return indexedDictionary.asMap(); } private String sort(String word) { List sortedCharacters= Arrays.asList(word.toCharArray()); Collections.sort(sortedCharacters); StringBuilder builder = new StringBuilder(); for (Character character : sortedCharacters) { builder.append(character); } return builder.toString(); } }
你可以这样做。
- 对每个单词进行排序，并将其添加到排序单词到实际单词的MultiMap中。
- 通过首先排序单词来查找每个单词以用作字谜。
索引成本是一次和O（N），其中N是单词的数量。
之后，排序成本为O（M log M），以对字母进行排序，其中M是字母数。 与计算排列的成本相比，这非常便宜。
BTW这种方法，这些单词只提前扫描一次。
这可以通过以下方式完成：
对于给定的单词，请记住其中的所有字符。 例如，对于OSTP，
count['O'] = 1; count['S'] = 1; count['T'] = 1; count['P'] = 1;
你可以像这样形成一个包含26个元素的数组。
然后在迭代字典时，只需检查哪个字具有相同的字符数。
您可以预处理您的列表：将其中的任何单词替换为其排序的字谜（即abacaba变为aaaabbc）。 此字符串唯一地表示任何单词，它是字典中单词的字谜。
然后，当您收到查询时，在其中对字母进行排序并检查此单词是否在预处理字典中。
为了获得最佳速度，您可以将字符映射到唯一的素数值，将它们相乘（确保您有足够大的数字），并将该产品用作存储有效排列的数字键。 每个数字对于给定的排列组是唯一的，因为字符形成唯一的主要分解。
给定一个输入词，重复该过程以获取该值，并直接使用该词访问该词典。 与排序字符串解决方案类似，但节省了排序的开销并简化了密钥比较。
另请参见此处了解c中的相关解决方案 – 为所有字谜生成相同的唯一哈希码