Python Solution with Trie

• My first post in discussion. This idea is kind of hard to follow if you didn't try on the same way by yourself before. Time complexity of current algorithm is not linear, but can be improved to guarantee linear even in worst case.

Build a Trie with words. When reach the end of the word, use "isword" to keep the index of the word. During adding a word to the Trie, if the rest of the word is palin, add the index of the word to key "ids" of that node.

Then for each word, look for the reverse of the word in the Trie. During searching for each word, if word ends but the trie path still continues, check the "ids" key of that node (node["ids"] keeps the index of the word which substring is palin after this node).

Check for empty string separately at last.

Current algorithm has a high worst case time complexity, but can be improved to guarantee O(n) (total number of characters of all words). I used a KMP method to calculate the suffix palin for each word in O(len(word)), and also for each reverse word. Therefore the ispalin can be check in O(1) after a linear preprocess for each word. However, that solution went TLE. The reason is: for the current algorithm, we don't need to do ispalin check for a good part of cases. However, for that preprocess method, we can't escape a linear preprocessing.

class Solution(object):

``````def ispalin(self, s):  # check if a string is palin (s is suffix of word in our case)
return s == s[::-1]

def palindromePairs(self, words):
result = []
root = {}  # use dict instead of a TrieNode class to save space
for i, word in enumerate(words):
curr = root
for idx, ch in enumerate(word):
if ch not in curr:
curr[ch] = {}
curr = curr[ch]
tmp = word[idx+1:]
if tmp and self.ispalin(tmp):
# keep the idx of word if the suffix of the word after current position is palin
curr.setdefault("ids", []).append(i)
curr["isword"] = i  # keep idx of word when reach the end
for j, word in enumerate(words):  # start searching reverse of each word in the Trie
w = word[::-1]
curr = root
fail = False
for idx, ch in enumerate(w):
if ch not in curr:
fail = True
break
curr = curr[ch]
# if current node is the end of some word, check whether the suffix of reverse word is palin
i = curr.get("isword")
if i is not None and i != j and self.ispalin(w[idx+1:]):
result.append([i, j])
if not fail and "ids" in curr:
result.extend([i, j] for i in curr["ids"] if i != j)
if "" in words:  # check for "" case
idx = words.index("")
result.extend(reduce(lambda x, y: x + y, ([[i, idx], [idx, i]] for i, w in enumerate(words) if w and self.ispalin(w))))
return result``````

• Good idea using a trie. I really liked how you handled the empty string case. Unfortunately you can't use `reduce()` in Python 3.x anymore.

However, it is true that using `dict` to store the trie may occupy less memory, but is waaaay less clear than using a class. Moreover, your code could be cleaner.

• @agave Would you please share your solution? I always learn much from your codes in various problems.

• @sbdust said in Python Solution with Trie:

@agave Would you please share your solution? I always learn much from your codes in various problems.

Thank you (if you like my posts, please do upvote them :) :) ).

This was my code (pretty ugly). But I don't like this problem, either.

``````class Solution(object):

def ispalin(self, s):  # check if a string is palin (s is suffix of word in our case)
return s == s[::-1]

def palindromePairs(self, words):
result = []
root = {}  # use dict instead of a TrieNode class to save space
for i, word in enumerate(words):
curr = root
for idx, ch in enumerate(word):
if ch not in curr:
curr[ch] = {}
curr = curr[ch]
tmp = word[idx+1:]
if tmp and self.ispalin(tmp):
# keep the idx of word if the suffix of the word after current position is palin
curr.setdefault("ids", []).append(i)
curr["isword"] = i  # keep idx of word when reach the end
for j, word in enumerate(words):  # start searching reverse of each word in the Trie
w = word[::-1]
curr = root
fail = False
for idx, ch in enumerate(w):
if ch not in curr:
fail = True
break
curr = curr[ch]
# if current node is the end of some word, check whether the suffix of reverse word is palin
i = curr.get("isword")
if i is not None and i != j and self.ispalin(w[idx+1:]):
result.append([i, j])
if not fail and "ids" in curr:
result.extend([i, j] for i in curr["ids"] if i != j)
if "" in words:  # check for "" case
idx = words.index("")
result.extend(reduce(lambda x, y: x + y, ([[i, idx], [idx, i]] for i, w in enumerate(words) if w and self.ispalin(w))))
return result
``````

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