java字符串排列组合查找

Question

我正在编写一个 Android 文字应用程序。我的代码包括一种方法，该方法可以找到字符串的所有组合和 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 s 上时，我意识到它运行起来有点太慢了。需要几秒钟才能完成。大约 3 或 4 秒，这是 Not Acceptable 。 现在我在手机上玩了一些文字游戏，它们立即计算出一个字符串的所有组合，这让我相信我的算法不是很有效并且可以改进。谁能帮忙？

---

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" 和单词列表 ["bad", "dab"]。现在，如果我们想找到 "dba" 的所有排列，我们将其排序为 "abd" 并在树中查找以检索列表。

正如 Baumann 指出的那样，tries非常适合存储此类数据。 trie 的美妙之处在于查找时间仅取决于搜索字符串的长度 - 它独立于字典的大小。由于您将存储相当多的单词，并且大部分搜索字符串都很小(大多数是来自递归最低级别的 3 个字符的子字符串)，因此这种结构是理想的。

在这种情况下，您的 trie 中的路径将反射(reflect)字符集而不是单词本身。因此，如果您的整个字典是 ["bad", "dab", "cab", "cable"]，您的查找结构最终将如下所示:

在您实现它的方式中有一点时间/空间的权衡。在最简单(也是最快)的方法中，每个 Node 仅包含单词列表和一个子数组 Node[26]。这允许您在恒定时间内找到您要找的 child ，只需查看 children[s.charAt(i)-'a'](其中 s 是你的搜索字符串和 i 是你当前在 trie 中的深度)。

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

使用 trie 树后，您的整个排列函数将被一次查找替换，从而将复杂度从 O(N!log D) 降低(其中 D 是字典的大小，N 字符串的大小)到 O(N log N)(因为您需要对字符进行排序；查找本身是 O (N)).

编辑: 我拼凑了这个结构的一个(未经测试的)实现:http://pastebin.com/Qfu93E80