Python Solution with Trie


  • 4
    C

    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

  • 0

    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.


  • 0
    S

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


  • 1

    @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
    

Log in to reply
 

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