给定一串字符时查找所有有效单词（递归/二进制搜索）

Question

我想要一些关于我尝试实施但并非 100% 有效的方法的反馈。我正在制作一个 Android 应用程序用于练习，其中为用户提供 20 个随机字母。然后用户使用这些字母组成任意大小的单词。然后它检查字典以查看它是否是有效的英语单词。给我带来麻烦的部分是显示 "hint"。如果用户卡住了，我想显示可能的单词。我最初想到的是递归。然而，对于 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

Is there a recommended, faster algorithm?

请参阅有关“String searching algorithm", in particular the section named "Algorithms using a finite set of patterns”的维基百科文章，其中 "finite set of patterns" 是您的字典。

第一个列出的 Aho–Corasick algorithm 可能是一个不错的选择。

Answer 2

加速算法的最简单方法可能是使用 Trie（前缀树）

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

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

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

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

给定一串字符时查找所有有效单词（递归/二进制搜索）

Find all valid words when given a string of characters (Recursion / Binary Search)

java

recursion

binary-search