如何对字符串生成的所有可能单词进行排序？

Question

我在想怎么进行这个任务，举个例子，比如这个字符串 "thingsandstuff"。

我该怎么从这个字符串中生成所有可能的字符串，然后逐个去查找英文词典呢？

目标是找到在没有空格的情况下，这个字符串中有效的英文单词。

谢谢！

Answer 1

暴力破解的方法，就是检查每一个子字符串，这种方法在处理中等长度的字符串时是不可行的（一个长度为 N 的字符串有 O(N**2) 个子字符串）。除非你关心的字符串长度有很严格的限制，否则这种方法不太适用。

为了让事情变得更可行，你需要更多的信息——你是想要找 重叠 的单词（比如你例子中的“things”和“sand”），还是想要那些会留下未处理字符的单词（比如“thing”和“and”，中间的“s”就没处理），还是你希望字符串被严格分割成不重叠的单词，没有任何剩余部分？

后者是最简单的问题，因为自由度大大降低——基本上就是要找出一系列“断点”，每个断点位于两个相邻字符之间，这样就能把字符串分割成单词。如果是这样的话，你需要每一种可能的有效分割（也就是说，你需要同时“thing sand”和“things and”），还是说只要有一个有效的分割就可以，或者你的分割需要满足某些优化标准？

如果你能澄清这些问题，可能会更容易给你提供帮助！

Answer 2

大家讨论这个问题时，常常把它看成是可能的子字符串数量，这其实是不对的。这个问题的正确复杂度是：

O( min ( 字典中的单词数量, 子字符串组合数量) * 比较成本)

所以，针对这个问题，另一种方法是对字典进行充分的索引（比如，对于字典中的每个单词，确定这个单词里的字母、单词的长度等等）。这样可以大大加快处理速度。举个例子，我们知道目标单词“queen”是无法和“zebra”匹配的（因为没有字母z！），也无法和任何包含字母z、r、b、a的单词匹配。此外，可以把字典中的每个单词存储为一个排序后的字符串（比如“zebra”变成“aberz”），然后进行“字符串在字符串中”的匹配（最长公共子字符串）。比如比较‘eenuq’和‘abarz’（没有匹配）。

（注意：我假设原单词中字母的顺序不重要——可以看作是一个“字母袋”，如果字母顺序重要，那就要相应调整）

如果你有很多单词需要同时比较，可以使用像KMP算法来进一步降低比较成本。

（另外，我直接开始了这个讨论，并做了一些假设，而Alex没有做，所以如果我说错了，那就请让我闭嘴吧！）

Answer 3

另一种可能性是反过来做，不是从一个字符串中生成子字符串，而是把所有候选单词拿出来，看看它们能否和你的字符串匹配。

你可以把匹配到的单词在原字符串中的起始和结束位置存储为一对对的索引。

这可以通过正则表达式轻松实现，或者如果正则表达式不够快，可以用str.find()方法，甚至如果还不够快，可以使用更复杂的字典索引方案，或者聪明地判断哪些可以匹配，哪些不可以（可以参考Gregg的回答获取一些想法）。

下面是我所说的一个示例

candidate = "thingsandstuffmydarlingpretty"
words = file('/usr/share/dict/words').read()
#This generator calls find twice, it should be rewritten as a normal loop
generate_matches = ((candidate.find(word),word) for word in words.split('\n')
                     if candidate.find(word) != -1 and word != '')

for match in generate_matches:
    print "Found %s at (%d,%d)" % (match[1],match[0],match[0] + len(match[1]))