s*******3
发帖数: 6 | 1 Given a list of words，find all palindrome pairs(two words that can build a
palindrome). For example, "ddcba" and "abc"are palindrome pairs, since they
can build "abcddcba" which is palindrome.
Follow up，可以组合任意个单词，怎么找到最长的可能的palindrome.
求指导，求讨论。 | x*******2
发帖数: 12 | 2 如果两个词能组成palindrome的话, 那reverse中间短的那个字符串应该是另一个的
prefix
能不能用trie, 然后在trie的node上记录在children都为palindrome的部分.
在建trie的时候, 插入一个string S, 就沿着root开始在S从后往前consume character：
1. 如果S有字符剩余, 那么就判断剩余字符串是否为palindrome, 并在trie的node上标记
2. 如果S没有字符串剩余了, 那返回当前是palindrome的那些字符串
不知道如何做followup... | s***5
发帖数: 2136 | 3 naïve solution for the original problem, O(n*n*avg(m)), n is # of words
, m is word length
follow-up should be a DP problem, but got confused on the recursive formula. | L*****1
发帖数: 34 | | j*****y
发帖数: 9 | | y**********a
发帖数: 824 | 6
然。 我就是这样被 fb 的变种题干掉的。
【在 j*****y 的大作中提到】
: 现在的题越出花样越多，刷题党都不好混了
| s**x
发帖数: 7506 | 7 以前讨论过的，关键是建立reverse 单词的trie.细节记不清了。 | p**p
发帖数: 742 | 8 Here is my two cents:
create two tries: trie1 with all words and trie2 with their reversed strings
. For each word, search in the trie1 with the reversed order and also in
trie2 with normal order. If we can find the trie node with the search orders
, do a DFS to find all words rooted at that node. Check all candidates to
see if they form a palindrome. |
|
