Let's assume we have two string

```
A: acbb
B: ca
```

We if we match reversed B and A we will find a match, which means AB could be a palindrome. However we still need to valid if the remain part of A is palindrome. In this case, yes, so AB is a correct answer. In the other case, B is longer than A

```
A: ac
B: bbca
```

We match reversed B and A. It's a match but we need to validate what's left with B. In this case, AB is also palindrome.

Matching and validation take O(k) time.

With tire(prefix tree), for each string A, we can find all possible B(string with same prefix to be validated) in near O(k) time. Actually it's O( average number of validated pair for each word ) time.

- Build tire tree
- For each word, reversed it and match the tire tree. Get all the possible matches and validate them.
- return

Here's a slow python code. No idea why it's slow maybe because my analyzation is wrong. LOL.

```
END = '11'
class Tire:
def __init__(self):
self.root = {}
def add(self, s, i):
tmp = self.root
for c in s:
if c not in tmp:
tmp[c] = {}
tmp = tmp[c]
tmp[END] = i
def match(self, s):
'''
retun all matched index
'''
tmp = self.root
rval = []
for c in s:
if END in tmp:
rval.append(tmp[END])
if c in tmp:
tmp = tmp[c]
else:
return rval
stack = [tmp]
while stack:
tmp = stack.pop()
if END in tmp:
rval.append(tmp[END])
for i in tmp.keys():
if i != END and tmp[i] is not str:
stack.append(tmp[i])
return rval
def isPali(s):
i,j = 0,len(s)-1
while i<=j:
if s[i]!=s[j]:
return False
i,j = i+1,j-1
return True
class Solution(object):
def palindromePairs(self, words):
"""
:type words: List[str]
:rtype: List[List[int]]
"""
rval = []
tire = Tire()
for i, w in enumerate(words):
tire.add(w,i)
for i, w in enumerate(words):
rw = w[::-1] #reverse word
for match_i in tire.match(rw):
if match_i != i:
match_w = words[match_i]
if len(match_w) <= len(w):
remain_w = rw[len(match_w):]
else:
remain_w = match_w[len(w):]
if isPali(remain_w):
rval.append([match_i, i])
return rval
```