我正在写一个Android单词应用程序。我的代码包含一个方法，该方法可以查找字符串和最小长度为 3 的 7 个字母字符串的子字符串的所有组合。然后将所有可用组合与字典中的每个单词进行比较，以找到所有有效单词。我正在使用递归方法。这是代码。
// 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);
}
}
}
在当前的方法中，您正在查找每个子字符串的每个排列。因此对于"abc"，你需要查找"abc", "acb", "bac", "bca", "cab" and "cba"。如果你想找到“排列”的所有排列，你的查找次数几乎是500,000,000，那是在您查看其子字符串之前。但我们可以将其简化为one通过预处理字典来查找，无论长度如何。
这个想法是将字典中的每个单词放入某种数据结构中，其中每个元素包含一组字符，以及包含（仅）这些字符的所有单词的列表。例如，您可以构建一个二叉树，其中包含一个包含（排序的）字符集的节点"abd"和单词列表["bad", "dab"]。现在，如果我们想找到所有排列"dba"，我们对其进行排序以给出"abd"并在树中查找以检索列表。
正如鲍曼指出的，tries非常适合存储此类数据。 trie 的美妙之处在于查找时间仅取决于搜索字符串的长度- 这是与字典的大小无关。由于您将存储相当多的单词，并且大多数搜索字符串都很小（大多数是来自递归最低级别的 3 字符子字符串），因此这种结构是理想的。
在这种情况下，特里树中的路径将反映字符集而不是单词本身。所以如果你的整个字典是["bad", "dab", "cab", "cable"]，您的查找结构最终将如下所示：
实现此方法时需要进行一些时间/空间权衡。在最简单（也是最快）的方法中，每个Node仅包含单词列表和一个数组Node[26]孩子的。这使您可以在恒定的时间内找到您正在寻找的孩子，只需查看children[s.charAt(i)-'a'] (where s是您的搜索字符串，并且i是您当前在 trie 中的深度）。
缺点是你的大部分children数组大部分是空的。如果空间是一个问题，您可以使用更紧凑的表示形式，例如链表、动态数组、哈希表等。但是，这些的代价是可能需要在每个节点进行多次内存访问和比较，而不是简单的数组访问上面。但如果整个字典中浪费的空间超过几兆字节，我会感到惊讶，因此基于数组的方法可能是您最好的选择。
使用 trie 后，整个排列函数将被一次查找所取代，从而将复杂性降低O(N!log D) (where D是你的字典的大小，N字符串的大小）到O(N log N)（因为您需要对字符进行排序；查找本身是O(N)).
EDIT:我已经整理了此结构的（未经测试的）实现：http://pastebin.com/Qfu93E80