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

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（前缀树）

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

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

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

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

Answer 2

是否有推荐，更快的算法？

参见“String searching algorithm”维基百科的文章，特别是部分命名为“Algorithms using a finite set of patterns”，其中“有限组模式”是你的字典。

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