检查一个单词是否由一个或多个连接的字典单词组成

Question

这是情景：

我有一个包含数百万个长度为3-32的随机字母字符串的数组和一个单词表（字典）数组。

我需要测试一个随机字符串是否可以由1、2或3个不同的字典单词连接而成。

由于字典单词会比较固定，因此我可以对它们进行任何类型的预处理。

理想情况下，我希望通过对字典进行某种类型的预处理来优化查找速度。

我应该考虑哪些数据结构/算法来实现这一点？

- Dogbert

---

所以它只能是1、2或3个单词（不能超过）？并且它必须是完整的随机字符串（不仅仅是一部分）？ - MacGucky

@MacGucky，我可能需要在以后支持4甚至5个单词。是的，它必须完全匹配。 - Dogbert

内存限制是什么？为什么不直接创建所有可能的组合并存储在Trie中？ - Aryabhatta

Answer 1

首先，从您的字典中构建一个Trie结构，每个根节点都映射到一个字母。然后，每个第二级子树都将拥有所有可以用两个字母组成的单词，以此类推。

接下来，从单词的第一个字母开始，沿着Trie向下查找，直到找到匹配项，然后递归地将此算法应用于单词的其余部分。如果在任何时候都找不到匹配项，则知道无法通过连接形成该单词。

- Andrew White

---

谢谢，我更新了我的答案。我忘记这个结构有一个正式的名称。 - Andrew White

由于贪心算法过于贪心，导致匹配失败。例如，如果你的字典包含“FORT”，“FORTY”和“TWO”，那么字符串“FORTYTWO”会匹配“FORT”，然后递归地检查“YTWO”，最终匹配失败。 - Martin DeMello

然后你会回溯并找到FORTY，然后是TWO。除非证明在特定子树中没有更多匹配项，否则搜索不会失败。在这种情况下，FORT子树至少有两个分支可尝试。 - Andrew White

你不需要回溯，只需使用合适的确定有限状态自动机（DFA）。 - R.. GitHub STOP HELPING ICE

你会使用哪种其他类型的DFA来帮助这个问题，R？ - f0ster

Answer 2

将字典字符串存储在散列集数据结构中。遍历要检查的字符串可能被分为1、2或3个部分的所有可能拆分，并对每个这样的拆分在散列集中查找所有部分。

- Sven Marnach

Answer 3

1. 使用正则表达式匹配字典中的每个单词。
2. 在它周围加上括号。
3. 在末尾加上一个 + 符号。
4. 使用任何正确（基于DFA）的正则表达式引擎编译它。

- R.. GitHub STOP HELPING ICE