LeetCode-Palindrome Pairs Solution

问题

Given a list of unique words, return all the pairs of the distinct indices (i, j) in the given list, so that the concatenation of the two words words[i] + words[j] is a palindrome.

Example 1:

Input:

 words = ["abcd","dcba","lls","s","sssll"]

Output:

 [[0,1],[1,0],[3,2],[2,4]]

Explanation:

 The palindromes are ["dcbaabcd","abcddcba","slls","llssssll"]

Example 2:

Input:

 words = ["bat","tab","cat"]

Output:

 [[0,1],[1,0]]

Explanation:

 The palindromes are ["battab","tabbat"]

Example 3:

Input:

 words = ["a",""]

Output:

 [[0,1],[1,0]]

Constraints:

• 1 <= words.length <= 5000
• 0 <= words[i].length <= 300
• words[i] consists of lower-case English letters.

解答

Trie：

时间复杂度O(nk^2)

1. 构造：Trie树的构造单词反序存放，并增加一个单词结束标识。
2. 匹配：
   • 当要查找单词A比当前Trie分支上的单词B长：前面匹配均成功，需要判断要找到单词A多出部分是不是回文。
   • 当要查找单词A比当前Trie分支上的单词B短：前面匹配均成功，需要判断该分支上的单词剩余部分是不是回文。

[“acbe”, “ca”, “bca”, “bbac”].

from https://fizzbuzzed.com/top-interview-questions-5/

class Solution:
    def getPalindromesForWord(self, trie, word, index):
        output = []
        while word:
            if trie.wordEndIndex >= 0:
                if isPalindrome(word):
                    output.append(trie.wordEndIndex)
            if not word[0] in trie.paths:
                return output
            trie = trie.paths[word[0]]
            word = word[1:]
        if trie.wordEndIndex >=0:
            output.append(trie.wordEndIndex)
        output.extend(trie.palindromesBelow)
        return output
    
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        trie = makeTrie(words)
        output=[]
        for i, word in enumerate(words):
            candidates = self.getPalindromesForWord(trie, word, i)
            output.extend([[i,c] for c in candidates if i!= c])
        return output

def isPalindrome(word):
    if len(word) == 0 or len (word) == 1:
        return True
    return word[0] == word[-1] and isPalindrome(word[1:-1])

class Trie:
    def __init__(self):
        self.paths = defaultdict(Trie)
        self.wordEndIndex = -1
        self.palindromesBelow = []
    def addWord(self, word, index):
        trie = self
        for j , char in enumerate(reversed(word)):
            if isPalindrome(word[0:len(word)-j]):
                trie.palindromesBelow.append(index)
            trie = trie.paths[char]
        trie.wordEndIndex = index

def makeTrie(words):
    trie = Trie()
    for i, word in enumerate(words):
        trie.addWord(word, i)
    return trie

穷举：

直接两层循环即可O(n^2k)

def isPalindrome(word):
    for i in range(len(word)//2):
        if word[i] != word[-1-i]:
            return False
    return True

def isPalindrome2(word):
    if len(word) == 0 or len(word) == 1:
        return True
    return word[0] == word[-1] and isPalindrome2(word[1:-1])

def isPalindrome3(word):
    return word == word[::-1]



def palidromePairs(words):
    output = []
    for i, firstword in enumerate(words):
        for j, secondword in enumerate(words):
            if (i == j):
                continue
            if isPalindrome3(firstword + secondword):
                output.append([i, j])
    return output

hash表：

思路和Trie是一致的只是单词是逆序存放到到hash表中， 分为两种情况：

1. 当前单词比要拼接的单词长
2. 当前单词比要拼接的单词短或者相等。

def palidromePairs(words):
    output = []
    word_to_index = {word: i for i, word in enumerate(words)}
    for i, firstword in enumerate(words):
        for j in range(len(firstword)+1):
            x_reversed = firstword[j:][::-1]
            rest = firstword[0:j]
            if isPalindrome(rest) and x_reversed in word_to_index and word_to_index[x_reversed] != i:
                output.append([word_to_index[x_reversed], i])

            if j == len(firstword): continue
            x_reversed = firstword[:j][::-1]
            rest = firstword[j:]
            if isPalindrome(rest) and x_reversed in word_to_index and word_to_index[x_reversed] != i:
                output.append([i, word_to_index[x_reversed]])
    return output

参考及引用

https://fizzbuzzed.com/top-interview-questions-5/

Photo by Josh Sorenson from Pexels