Palindrome Pairs怎么能O(n*k)解？

Leetcode 336. Palindrome Pairs，我用Trie来做，先把每个单词倒序插入Trie。对于每个单词插完一个字母，判断剩下的是否为Palindrome，如果是的话标记index。这样每插一个单词就需要O(k^2)，一共需要O(n*k^2)。Trie建好后再扫一遍输入，对每个单词正序去Trie里找。如果在某个字母到达叶子，则判断剩下的是否为Palindrome，如果是就输出到Result。这一步对每个单词也是O(k^2)，一共需要O(n*k^2)。总的下来就是O(n*k^2)。
感觉k^2部分可以优化，因为对每个单词的每个字母判断剩下的是否为Palindrome太浪费了。但是不知道怎么优化。


面试官提示说有O(n*k)的解法，说可以用两个Trie搞定，不过没想明白怎么搞。谁能指点一下？多谢！

我用我说的O(n*k^2)的方法，在Leetcode上耗时249ms，只beat 27%。剩下那73%都是怎么做的呢？是不是就是O(n*k)的方法？

前几天刚刷到这题
搜一下就能找到，O(n)一遍扫描判断一个字符串的所有前缀是不是回文串：https://www.geeksforgeeks.org/online-algorithm-for-checking-palindrome-in-a-stream/
顺便看了一下时间分布，249ms处于主峰右侧，不算慢了。同一个峰之内的解，渐近时间复杂度一般都是一样的，差异只在于实现细节导致常数不同

两个trie 一个正序存储单词 一个逆序存储单词 然后分别遍历 对比

补充内容 (2018-10-28 22:52):
好像不对