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

Question

这是场景:

我有一个数百万长度为3-32的随机字符串数组,以及一个单词数组(字典).

我需要测试是否可以通过连接1,2或3个不同的字典单词来组成随机字符串.

由于字典单词有些固定,我可以对它们进行任何类型的预处理.

理想情况下,我想通过对字典进行某种预处理来优化查找速度.

我应该考虑采用哪种数据结构/算法来实现这一目标？

Answer 1

首先,从你的词典中构建一个像 Trie结构的B树.每个根都会映射到一个字母.然后,每个第二级子树将包含可以用两个字母组成的所有单词,依此类推.

然后接受你的话,从第一个字母开始,沿着B-Tree Trie走,直到你找到一个匹配,然后递归地将这个算法应用到单词的其余部分.如果您在任何时候都找不到匹配项,则您知道无法通过concats形成单词.