从单词列表构造回文
Constructing palindrome from a list of words
最近在翻一些面试题，发现了一个比较有意思的：
你得到了一个单词列表。找出两个单词是否可以连接在一起形成回文。例如，考虑一个列表 {bat, tab, cat} 然后 bat 和 tab 可以连接在一起形成一个回文。
期待一个 O(nk) 解决方案，其中 n = 作品数量，k 是长度
可以有多对，只有 return 如果找到一对则为真。
此外，在评论中，其中一种方法是这样的：
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)看是不是回文如果是就完了return true
5) 将第二个单词添加到 trie (D E E D B A)
6) 使用下一个单词
返回步骤 2
7) 出词时 return false
但在我看来这不是 O(nk) 解决方案。
谁能提出解决方案？？或者解释为什么上面描述的算法是O(nk)??
算法是正确的，或者至少非常接近。有一些小的技术问题。在第 4 步中，如果它比当前的解决方案更好，则应保存该解决方案的命题，并在第 7 步中 return 它，或者说不可能构成回文。
主要思想是将单词处理成核心和前缀。如果核心是回文，那么我们需要将前缀与其他单词匹配。 Trie 用作已处理字符串的 "database"，因此对于每个新词，都可以检查所有可能的扩展名。如果单词分开保存，则需要分别比较每个单词的前缀。
(编辑：我认为还是有一个小漏洞，万一一个trie中有两个单词开头相同，进来的单词会和较短的那个形成回文，但是不会越长，但我不会详细说明。处理它会使算法复杂化，但不会影响复杂度。)
也是O(n*k)。添加和检查前缀与 trie 需要的步骤数与字符数成正比。所以在这种情况下，this 受 k 约束。就像树操作是 O(h)，其中 h 是树的高度。所以总而言之：
k 步。
走 k 步。
最多也需要 k 步。
也需要少于 k 步，但我们可以通过 k.
也需要 k 步。
步骤 2 到 5 已完成 n-1 次。
当然每一步都有不同的显性操作，所以很难指定确切的常数，但它们都受k约束，所以复杂度是O(c*(n-1)*k)，本质上是O(n*k).
2004 年 Dr. Dobbs 的一篇文章对此进行了非常有趣的讨论。完整的解释有点长，但总体思路是：
Suppose you start with Lion, where the pivot is left of the actual word. I can calculate the center of the string, which is position two. The pivot is at zero, so the string is too heavy on the right, but at the moment, Lion qualifies as a partial palindrome. The "dot" at the pivot point matches the dot at the pivot point, so there is at least one correct character, albeit the same character. You now wish to prepend words that end with noil, attempting to convert the string to noil.Lion. I use to mean any string of characters. If you're successful, then you need to locate words starting with so that they can be appended to the string.
注意他将部分回文定义为：
A string is a partial palindrome if, working from the pivot point outwards, either the left or right end of the string is encountered before a mismatch occurs.
最近在翻一些面试题，发现了一个比较有意思的：
你得到了一个单词列表。找出两个单词是否可以连接在一起形成回文。例如，考虑一个列表 {bat, tab, cat} 然后 bat 和 tab 可以连接在一起形成一个回文。 期待一个 O(nk) 解决方案，其中 n = 作品数量，k 是长度
可以有多对，只有 return 如果找到一对则为真。
此外，在评论中，其中一种方法是这样的：
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)看是不是回文如果是就完了return true
5) 将第二个单词添加到 trie (D E E D B A)
6) 使用下一个单词
返回步骤 2
7) 出词时 return false
但在我看来这不是 O(nk) 解决方案。
谁能提出解决方案？？或者解释为什么上面描述的算法是O(nk)??
算法是正确的，或者至少非常接近。有一些小的技术问题。在第 4 步中，如果它比当前的解决方案更好，则应保存该解决方案的命题，并在第 7 步中 return 它，或者说不可能构成回文。
主要思想是将单词处理成核心和前缀。如果核心是回文，那么我们需要将前缀与其他单词匹配。 Trie 用作已处理字符串的 "database"，因此对于每个新词，都可以检查所有可能的扩展名。如果单词分开保存，则需要分别比较每个单词的前缀。
(编辑：我认为还是有一个小漏洞，万一一个trie中有两个单词开头相同，进来的单词会和较短的那个形成回文，但是不会越长，但我不会详细说明。处理它会使算法复杂化，但不会影响复杂度。)
也是O(n*k)。添加和检查前缀与 trie 需要的步骤数与字符数成正比。所以在这种情况下，this 受 k 约束。就像树操作是 O(h)，其中 h 是树的高度。所以总而言之：
k步。走
k步。最多也需要
k步。也需要少于
k步，但我们可以通过k. 来限制它
也需要
k步。
步骤 2 到 5 已完成 n-1 次。
当然每一步都有不同的显性操作，所以很难指定确切的常数，但它们都受k约束，所以复杂度是O(c*(n-1)*k)，本质上是O(n*k).
2004 年 Dr. Dobbs 的一篇文章对此进行了非常有趣的讨论。完整的解释有点长，但总体思路是：
Suppose you start with Lion, where the pivot is left of the actual word. I can calculate the center of the string, which is position two. The pivot is at zero, so the string is too heavy on the right, but at the moment, Lion qualifies as a partial palindrome. The "dot" at the pivot point matches the dot at the pivot point, so there is at least one correct character, albeit the same character. You now wish to prepend words that end with noil, attempting to convert the string to noil.Lion. I use to mean any string of characters. If you're successful, then you need to locate words starting with so that they can be appended to the string.
注意他将部分回文定义为：
A string is a partial palindrome if, working from the pivot point outwards, either the left or right end of the string is encountered before a mismatch occurs.