# Tire and almost same logic with others

• 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.

1. Build tire tree
2. For each word, reversed it and match the tire tree. Get all the possible matches and validate them.
3. 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 = {}

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):

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
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.