java字符串排列和组合查找

java字符串排列和组合查找

在当前方法中，您正在查找每个子字符串的每个排列。因此，对

"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