算法问题在发现所有有效字在字典 [英] Algorithm Question On Finding All Valid Words In Dictionary

问题描述

由于字典（只是一个字符串列表）。

Given a dictionary (just a list of strings).

您收到来自外部源的进料的数目不详的信件。鉴于字母串，你将如何去列出所有有效字（从diciontary），你可以从这些字母的任意组合。

You receive a feed of an unknown number of letters from an external source. Given the string of letters, how would you go about listing all valid words (from the diciontary) you can make from any combination from those letters.

因此​​，如果您收到：abpplead

So if you receive: abpplead

您应该找到苹果，坏，垫，铅，等等。

You should find apple, bad, pad, lead, etc.

我知道有没有最佳答案。但是，有一些合理有效的方法来做到这一点，使用什么数据结构等。

I know there's no best answer. But what are some reasonably efficient ways to do it, what data structures to use, etc.

此外，假定你可以pre-流程的输入，这样你就可以选择存储输入的字母，因为他们进来的任何数据结构，你想要的。

Also, assume you can pre-process the input, so you can choose to store the input letters as they come in in whatever data structure you want.

推荐答案

把字典转为线索。然后把信成以他们的品格值索引的计数器阵列，保持计数每一个字母（姑且称之为计数[]）。然后遍历深度优先搜索顺序线索，递减计数[信]值的每个字母，同时穿越向下，并递增它在回来的路上了。现在，任何时候计数[信]即将变为负，停止和穿越回以上。任何时候你达到一个字终止，输出结果。

Put the dictionary into a trie. Then put the letters into an counter array indexed by their character values, maintaining the counts for each letter (let call this counts[]). Then traverse the trie in depth first search order, decrementing the counts[letter] value for each letter while traversing downward, and incrementing it on the way back up. Now, any time a counts[letter] is about to go negative, stop and traverse back upwards. Any time you reach a word terminator, output the result.

这篇关于算法问题在发现所有有效字在字典的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！