时间复杂度是多少？我只是想避免这是O(n!)。使用深度优先搜索是否会是时间复杂度O(n^2)，因为对于每个字母，它可能必须通过所有其他字母最坏的情况？
我想我不确定我是否以正确的方式考虑这个问题。
当我说使用深度优先搜索时，我的意思是从第一个字母开始深度优先搜索，然后从第二个字母开始，等等。
那有必要吗？
注意：
最初的问题是在填字游戏/拼图板上找到所有可能的单词。我正在考虑使用 trie 数据结构来查找字典中是否有单词，但我正在考虑自己生成单词的方法。
问问题
932 次
1 回答
0
根据上面的讨论，这是我的答案：
定义：atrieX是一个子树，只有长度的单词X。
由于我们有一个包含所需语言的所有单词的 trie，我们也可以获得适当的trieX.
我们说填字游戏有w单词，所以我们创建一个 long 数组w，其中每个条目是 trieX 的根，其中X是相关单词的长度。这为我们提供了每个空白单词中可能出现的单词列表。
然后迭代单词之间的交集并消除无法放置的单词。当没有更多更改完成时 - 我们停止。
两点意见：
1. 为了提高性能，我们从添加长词或非常短的词开始。什么是短或长？看看这个和这个。
2. 从 trieX 中删除词也可以通过检查词之间的依赖关系来完成（如果 THIS 词在这里，那么 THAT 词不能在那里，等等）。这更复杂，所以如果有人想添加一些关于如何轻松做到这一点的想法 - 请这样做。
于 2015-06-11T07:33:57.190 回答