在给定一串字符时查找所有有效单词(递归/二叉搜索)

Question

我想对我尝试实现的方法提供一些反馈，该方法无法 100% 工作。我正在制作一个用于练习的Android应用程序，其中用户会得到20个随机字母。然后，用户使用这些字母来制作任何大小的单词。然后，它会检查字典以查看它是否是有效的英语单词。 给我带来麻烦的部分是显示"提示"。如果用户卡住了，我想显示可以制作的可能单词。我最初认为递归。但是，对于 20 个字母，这可能需要相当长的时间才能执行。因此，我还实现了二叉搜索来检查当前的递归路径是否是字典中任何内容的前缀。我确实得到了有效的提示输出，但它没有返回所有可能的单词。我的递归思维有误吗？另外，是否有推荐的更快算法？我见过一种方法，你可以检查字典中的每个单词，看看字符是否可以组成每个单词。但是，我想知道我的方法与那个方法相比有多有效。

private static void getAllWords(String letterPool, String currWord) {
//Add to possibleWords when valid word
if (letterPool.equals("")) {
//System.out.println("");
} else if(currWord.equals("")){
for (int i = 0; i < letterPool.length(); i++) {
String curr = letterPool.substring(i, i+1);
String newLetterPool = (letterPool.substring(0, i) + letterPool.substring(i+1));
if(dict.contains(curr)){
possibleWords.add(curr);
}
boolean prefixInDic = binarySearch(curr);
if( !prefixInDic ){
break;
} else {
getAllWords(newLetterPool, curr);
}
}
} else {
//Every time we add a letter to currWord, delete from letterPool
//Attach new letter to curr and then check if in dict
for(int i=0; i<letterPool.length(); i++){
String curr = currWord + letterPool.substring(i, i+1);
String newLetterPool = (letterPool.substring(0, i) + letterPool.substring(i+1));
if(dict.contains(curr)) {
possibleWords.add(curr);
}
boolean prefixInDic = binarySearch(curr);
if( !prefixInDic ){
break;
} else {
getAllWords(newLetterPool, curr);
}
}
}
private static boolean binarySearch(String word){
int max = dict.size() - 1;
int min = 0;
int currIndex = 0;
boolean result = false;
while(min <= max) {
currIndex = (min + max) / 2;
if (dict.get(currIndex).startsWith(word)) {
result = true;
break;
} else if (dict.get(currIndex).compareTo(word) < 0) {
min = currIndex + 1;
} else if(dict.get(currIndex).compareTo(word) > 0){
max = currIndex - 1;
} else {
result = true;
break;
}
}
return result;
}

Answer 1

加快算法速度的最简单方法可能是使用 Trie(前缀树)

Trie 数据结构提供了两种相关的方法。 isWord(String) 和 isPrefix(String)，两者都需要 O(n) 比较来确定字典中是否存在单词或前缀(其中 n 是参数中的字母数)。这真的很快，因为你的字典有多大并不重要。

为了进行比较，使用二叉搜索检查字典中是否存在前缀的方法是 O(n*log(m))，其中 n 是字符串中的字母数，m 是字典中的单词数。

我使用 Trie 编写了与您类似的算法，并将其与您在一个非常非正式的基准测试中发布的代码(稍作修改)进行了比较。 使用20字符输入，Trie需要9ms。原始代码没有在合理的时间内完成，所以我不得不杀死它。

编辑： 至于为什么你的代码不返回所有提示，如果前缀不在字典中，你不想中断。您应该继续检查下一个前缀。

Answer 2

有没有推荐的、更快的算法？

请参阅维基百科关于"字符串搜索算法"的文章，特别是名为"使用有限模式集的算法"的部分，其中"有限模式集"是您的字典。

首先列出的Aho-Corassick算法可能是一个不错的选择。