336. Palindrome Pairs

逻辑

You are given a 0-indexed array of unique strings words.

A palindrome pair is a pair of integers (i, j) such that:

• 0 <= i, j < words.length,

• i != j, and

• words[i] + words[j] (the concatenation of the two strings) is a palindrome.

Return an array of all the palindrome pairs of words.

You must write an algorithm with O(sum of words[i].length) runtime complexity.

Example 1:

Input: words = ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]
Explanation: The palindromes are ["abcddcba","dcbaabcd","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]]
Explanation: The palindromes are ["a","a"]

Constraints:

• 1 <= words.length <= 5000

• 0 <= words[i].length <= 300

• words[i] consists of lowercase English letters.

分析

把每个word拆两段， 一段是回文的话， 只需要前后加入的词是另一段的回文即可

判断是否回文 内置函数快 word == word[::-1]

# reversed suffix(w1) + prefix(is palindrome)+ suffix
# prefix + suffix(is palindrome) + reversed prefix(w1)

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        wordmap = {w:i for i, w in enumerate(words)}
        res = []      

        for i, w in enumerate(words):
            for j in range(len(w)+1):
                prefix = w[:j]
                suffix = w[j:]
               # reversed suffix(w1) + prefix(is palindrome)+ suffix
                if prefix == prefix[::-1]:
                    reversed_suffix = suffix[::-1]
                    if j>0 and reversed_suffix in wordmap and wordmap[reversed_suffix] != i:
                        res.append([wordmap[reversed_suffix], i])
                # prefix + suffix(is palindrome) + reversed prefix(w1)
                if suffix == suffix[::-1]:
                    reversed_prefix = prefix[::-1]
                    if reversed_prefix in wordmap and wordmap[reversed_prefix] != i:
                        res.append((i, wordmap[reversed_prefix]))
        return res