java字符串排列和组合查找

Question

我正在编写一个 Android
word应用程序。我的代码包含一个方法，该方法将查找字符串和7个字母的字符串的子字符串的所有组合，且其最小长度为3。然后将所有可用组合与字典中的每个单词进行比较，以找到所有有效单词。我正在使用递归方法。这是代码。

// Gets all the permutations of a string.
void permuteString(String beginningString, String endingString) {
    if (endingString.length() <= 1){
        if((Arrays.binarySearch(mDictionary, beginningString.toLowerCase() +   endingString.toLowerCase())) >= 0){
            mWordSet.add(beginningString + endingString);
        }
    }
    else
        for (int i = 0; i < endingString.length(); i++) {
            String newString = endingString.substring(0, i) + endingString.substring(i + 1);
            permuteString(beginningString + endingString.charAt(i), newString);
      }
}
// Get the combinations of the sub-strings. Minimum 3 letter combinations
void subStrings(String s){
    String newString = "";
    if(s.length() > 3){
        for(int x = 0; x < s.length(); x++){
            newString = removeCharAt(x, s);
            permuteString("", newString);
            subStrings(newString);
        }
    }
}

上面的代码运行正常，但是当我将其安装在Nexus上时，我意识到它的运行速度太慢了。这需要几秒钟才能完成。大约3或4秒，这是不可接受的。现在，我在手机上玩了一些文字游戏，它们可以立即计算出字符串的所有组合，这使我相信我的算法不是很有效，可以改进。有人可以帮忙吗？

public class TrieNode {
TrieNode a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z;
TrieNode[] children = {a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z};
private ArrayList<String> words = new ArrayList<String>();

public void addWord(String word){
    words.add(word);
}
public ArrayList<String> getWords(){
    return words;
}
}

public class Trie {

static String myWord;
static String myLetters = "afinnrty";
static char[] myChars;
static Sort sort;
static TrieNode myNode = new TrieNode();
static TrieNode currentNode;
static int y = 0;
static ArrayList<String> availableWords = new ArrayList<String>();

public static void main(String[] args) {

    readWords();
    getPermutations();
}
public static void getPermutations(){
    currentNode = myNode;
    for(int x = 0; x < myLetters.length(); x++){
        if(currentNode.children[myLetters.charAt(x) - 'a'] != null){
            //availableWords.addAll(currentNode.getWords());
            currentNode = currentNode.children[myLetters.charAt(x) - 'a'];
            System.out.println(currentNode.getWords() + "" + myLetters.charAt(x));
        }
    }
    //System.out.println(availableWords);
}
public static void readWords(){
    try {
        BufferedReader in = new BufferedReader(new FileReader("c://scrabbledictionary.txt"));
        String str;
        while ((str = in.readLine()) != null) {
            myWord = str;
            myChars = str.toCharArray();
            sort = new Sort(myChars);
            insert(myNode, myChars, 0);
        }
        in.close();
    } catch (IOException e) {
    }
}
public static void insert(TrieNode node, char[] myChars, int x){    
    if(x >= myChars.length){
        node.addWord(myWord);
        //System.out.println(node.getWords()+""+y);
        y++;
        return;
    }
    if(node.children[myChars[x]-'a'] == null){
        insert(node.children[myChars[x]-'a'] = new TrieNode(), myChars, x=x+1);
    }else{
        insert(node.children[myChars[x]-'a'], myChars, x=x+1);
    }
}
}

Answer 1

在当前方法中，您正在查找每个子字符串的每个排列。因此，对"abc"，你需要仰视"abc"，"acb"，"bac"，"bca"，"cab"和"cba"。如果要查找“排列”的所有排列，则查询数量接近
500,000,000 ，而这甚至还没有查看其子字符串。但是我们可以通过预处理字典将 其 减少为 一次
查询，而不论其长度如何。

想法是将字典中的每个单词放入某种数据结构中，其中每个元素包含一组字符，以及包含（仅）那些字符的所有单词的列表。因此，例如，您可以构建一个二叉树，该树将具有一个包含（排序的）字符集"abd"和单词list
的节点["bad", "dab"]。现在，如果要查找的所有排列"dba"，我们将其排序以给出"abd"并在树中查找以检索列表。

正如鲍曼指出的那样，尝试非常适合存储此类数据。特里树的优点是查找时间
仅取决于搜索字符串的长度， 它 与字典的大小无关
。由于您将存储很多单词，并且您的大多数搜索字符串都很小（大多数将是递归最低级别的3个字符的子字符串），因此这种结构是理想的。

在这种情况下，指向特里的路径将反映字符集而不是单词本身。因此，如果您的整个字典是["bad", "dab", "cab", "cable"]，那么您的查找结构将最终看起来像这样：

实施此方法时，需要进行一些时间/空间的权衡。在最简单（也是最快）的方法中，每个Node仅包含单词列表和一系列Node[26]子代。这样一来，您只需查看即可即可找到您要寻找的孩子children[s.charAt(i)-'a']（在哪里s，您的搜索字符串，以及i您当前在Trie中的深度）。

不利的一面是您的大多数children阵列将大部分为空。如果空间不足，可以使用更紧凑的表示形式，例如链表，动态数组，哈希表等。但是，这些代价是可能需要在每个节点上进行多次内存访问和比较，而不是简单的数组访问上方。但是，如果浪费的空间超过整个字典的几兆字节，我会感到惊讶，因此基于数组的方法可能是最好的选择。

放置特里树后，您的整个排列函数将被一次查找替换，从而使复杂度从 O（N！log D） （其中 D 是字典的大小， N
是字符串的大小）降低到 O（N log N） （因为您需要对字符进行排序；查找本身是 O（N） ）。

编辑： 我把这个结构的（未测试的）实现放在一起：http :
//pastebin.com/Qfu93E80