KMP solution in Python


  • 0
    O
        def _LPS(self, s):
            '''
            s: str
            '''
            # compute LPS
            s_reversed = s[::-1]
            s_cat = s + '#' + s_reversed
            # auxiliary LPS array
            lps = [0] * len(s_cat)
            q = 0
            for i in range(1, len(s_cat)):
                # print(q, s_cat[q], s_cat[i])
                while q and s_cat[q] != s_cat[i]:
                    q = lps[q - 1]
                if s_cat[q] == s_cat[i]:
                    q += 1
                lps[i] = q
            l = lps[-1]
            while l:
                yield l
                l = lps[l - 1]
            yield l
    
        def palindromePairsKMP(self, words: list):
            word2idx = {t[1]: t[0] for t in enumerate(words)}
            pairs = set()
            for j, _ in enumerate(words):
                # find palindrome prefix/suffix of words[j], 
                # reverse the remaining part,
                # check its existence in the word2idx
                for prefix_len in self._LPS(words[j]):
                    remaining = words[j][prefix_len:][::-1]
                    i = word2idx.get(remaining)
                    if i is not None and i != j: pairs.add((i, j))
    
                for prefix_len in self._LPS(words[j][::-1]):
                    remaining = words[j][:len(words[j]) - prefix_len][::-1]
                    i = word2idx.get(remaining)
                    if i is not None and i != j: pairs.add((j, i))
            pairs = sorted(map(lambda x: list(x), pairs))
            print(pairs)
            return pairs
    

Log in to reply
 

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