c++ - 从单词列表构造回文

Question

最近在翻一些面试题，发现了一个比较有意思的:

给你一个单词列表。找出两个单词是否可以连接在一起形成回文。例如，考虑一个列表 {bat, tab, cat} 然后 bat 和 tab 可以连接在一起形成一个回文。期待一个 O(nk) 的解决方案，其中 n = 作品数量，k 是长度

可以有多个对，找到一个就返回true。

此外，在评论中，其中一种方法是这样的:

1) 将第一个单词添加到 trie ( A B )
2) 取第二个字(D E E D B A) 反转(A B D E E D)
3) 看看你能在trie中匹配出多少个反向单词中的字母(前2个)
4) 取出字符串的其余部分 (D E E D) 看它是否是回文如果是则返回 true
5) 将第二个单词添加到 trie (D E E D B A)
6) 使用下一个单词返回步骤 2
7) 出词时返回false

但在我看来这不是 O(nk) 解决方案。

谁能提出解决方案？？或者解释为什么上面描述的算法是O(nk)？？

Answer 1

算法是正确的，或者至少非常接近。有一些小的技术问题。在第 4 步中，如果解决方案比当前解决方案更好，则应该保存该解决方案的命题，并在第 7 步中返回它，或者说不可能形成回文。

主要思想是将单词处理成核心和前缀。如果核心是回文，那么我们需要将前缀与其他单词匹配。 Trie 用作处理过的字符串的“数据库”，因此对于每个新词，都可以检查所有可能的扩展名。如果单词分开保存，则需要分别比较每个单词的前缀。

(编辑:我认为还有一个小漏洞，万一一个 trie 中有两个词开头相同，传入的词会与较短的词形成回文，但不会与较长的词形成回文，但我不会详细介绍。处理它会使算法复杂化，但不会影响复杂性。)

它也是 O(n*k)。添加和检查前缀与 trie 需要的步骤数与字符数成正比。所以在这种情况下，this 受 k 约束。就像树操作是 O(h)，其中 h 是树的高度。所以总而言之:

1. k 个步骤。

2. 走 k 步。

3. 最多也需要 k 步。

4. 也需要少于 k 个步骤，但我们可以用 k 来限制它。

5. 也需要 k 步。

第 2 步到第 5 步执行了 n-1 次。

当然每一步都有不同的主导操作，所以很难指定确切的常数，但它们都受 k 的约束，所以复杂度是 O(c*( n-1)*k) 本质上是 O(n*k)。