java字符串排列和组合查找

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

// Gets all the permutations of a string. void permuteString(String beginningString, String endingString) { if (endingString.length() = 0){ mWordSet.add(beginningString + endingString); } } else for (int i = 0; i  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 words = new ArrayList(); public void addWord(String word){ words.add(word); } public ArrayList 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 availableWords = new ArrayList(); public static void main(String[] args) { readWords(); getPermutations(); } public static void getPermutations(){ currentNode = myNode; for(int x = 0; 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指出的那样， 尝试非常适合存储这类数据。 trie的美妙之处在于查找时间仅取决于搜索字符串的长度 – 它与字典的大小无关 。 由于您将存储相当多的单词，并且您的大多数搜索字符串都很小（大多数将是递归最低级别的3个字符的子字符串），因此这种结构非常理想。

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

实现这一点的方式有一些时间/空间权衡。 在最简单（也是最快）的方法中，每个Node仅包含单词列表，以及子Node[26]的子Node[26] 。 这样你就可以通过查看children[s.charAt(i)-'a'] （其中s是你的搜索字符串， i是你在trie中的当前深度）来定位你所经历的孩子。

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

随着trie的到位，你的整个排列函数被一个查找替换，从而将复杂性从O（N！log D） （其中D是字典的大小， N是字符串的大小）降低到O（N log） N） （因为你需要对字符进行排序;查找本身是O（N） ）。

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

Answer 2

请参见： 如何从字母矩阵中找到可能的单词列表[Boggle Solver]

答案中代码背后的想法如下：

• 迭代每个单词字典。
• 迭代单词中的每个字母，将其添加到字符串并每次将字符串添加到前缀数组中。
• 创建字符串组合时，请在进一步分支之前测试它们是否存在于前缀数组中。

Answer 3

  static List permutations(String a) { List result=new LinkedList(); int len = a.length(); if (len<=1){ result.add(a); }else{ for (int i=0;i 

Answer 4

我不认为添加所有排列是必要的。 您可以简单地将字符串封装到PermutationString ：

 public class PermutationString { private final String innerString; public PermutationString(String innerString) { this.innerString = innerString; } @Override public int hashCode() { int hash = 0x00; String s1 = this.innerString; for(int i = 0; i < s1.length(); i++) { hash += s1.charAt(i); } return hash; } @Override public boolean equals(Object obj) { if (obj == null) { return false; } if (getClass() != obj.getClass()) { return false; } final PermutationString other = (PermutationString) obj; int nChars = 26; int[] chars = new int[nChars]; String s1 = this.innerString; String s2 = other.innerString; if(s1.length() != s2.length()) { return false; } for(int i = 0; i < s1.length(); i++) { chars[s1.charAt(i)-'a']++; } for(int i = 0; i < s2.length(); i++) { chars[s2.charAt(i)-'a']--; } for(int i = 0; i < nChars; i++) { if(chars[i] != 0x00) { return false; } } return true; } } 

PermutationString是一个字符串，但如果两个PermutationString具有相同的字符频率，则它们相等。 因此new PermutationString("bad").equals(new PermutationString("dab")) 。 这也适用于.hashCode() ：如果字符串是彼此的排列，它们将生成相同的.hashCode() 。

现在您可以简单地使用HashMap> ，如下所示：

 HashMap> hm = new HashMap>(); String[] dictionary = new String[] {"foo","bar","oof"}; ArrayList items; for(String s : dictionary) { PermutationString ps = new PermutationString(s); if(hm.containsKey(ps)) { items = hm.get(ps); items.add(s); } else { items = new ArrayList(); items.add(s); hm.put(ps,items); } } 

所以现在我们迭代字典中的所有可能的单词，构造一个PermutationString作为键 ，如果键已经存在（这意味着已经有一个具有相同字符频率的单词），我们只需添加我们自己的单词。 否则，我们使用单个单词添加一个新的ArrayList 。

现在我们已经用所有排列填充了hm （但没有那么多键 ），你可以查询：

 hm.get(new PermutationString("ofo")); 

这将返回带有"foo"和"oof"的ArrayList 。

测试用例 ：

 HashMap> hm = new HashMap>(); String[] dictionary = new String[]{"foo", "bar", "oof"}; ArrayList items; for (String s : dictionary) { PermutationString ps = new PermutationString(s); if (hm.containsKey(ps)) { items = hm.get(ps); items.add(s); } else { items = new ArrayList(); items.add(s); hm.put(ps, items); } } Assert.assertNull(hm.get(new PermutationString("baa"))); Assert.assertNull(hm.get(new PermutationString("brr"))); Assert.assertNotNull(hm.get(new PermutationString("bar"))); Assert.assertEquals(1,hm.get(new PermutationString("bar")).size()); Assert.assertNotNull(hm.get(new PermutationString("rab"))); Assert.assertEquals(1,hm.get(new PermutationString("rab")).size()); Assert.assertNotNull(hm.get(new PermutationString("foo"))); Assert.assertEquals(2,hm.get(new PermutationString("foo")).size()); Assert.assertNotNull(hm.get(new PermutationString("ofo"))); Assert.assertEquals(2,hm.get(new PermutationString("ofo")).size()); Assert.assertNotNull(hm.get(new PermutationString("oof"))); Assert.assertEquals(2,hm.get(new PermutationString("oof")).size()); 

Answer 5

使用Trie

而不是测试所有N！ 可能性，您只需遵循导致结果的前缀树。 这将显着减少您要检查的字符串数量。

Answer 6

好吧，你可以使用数组letters[]扩展你的字典实体，其中letters[i]保留的时间是这个单词中使用的第i个字母。 它需要一些额外的内存，并不比现在使用的多。

然后，对于要检查的排列的每个单词，您还需要计算不同字母的数量，然后通过简单的比较程序遍历分类。 如果对于字典中所有字母的所有字母数量少于或等于字词我们正在检查 – 是的，这个字可以表示为子字符串的排列，否则 – 否。

复杂性：预先计算需要O（D * maxLen），每个查询需要O（max（N，D））。