Tire and almost same logic with others


  • 0
    C

    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 = {}
            
        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
    

Log in to reply
 

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