動機

Hard題都是來看創意的

中間是回文，前半是後面的reverse

Problem

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.

Sol

回文

  1. 前半是後面的reverse (反之亦然)
  2. 中間是回文，前半是後面的reverse (反之亦然)

這樣就不用一個一個去對了，可以善用dict

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        def palind(s):
            return s == s[::-1]
        
        ws = {w[::-1]: i for (i,w) in enumerate(words) if w}
        ret = []
        for (i,w1) in enumerate(words):
            if not w1: #empty
                ret += sum([[[i,j],[j,i]] for (j,w2) in enumerate(words) if i!=j and palind(w2)],[])
            else:
                # total word
                if w1 in ws and ws[w1] != i:
                    ret.append([i,ws[w1]])
                for x in range(1,len(w1)):
                    l,r = w1[:x],w1[x:]
                    # left is center
                    if palind(l) and r in ws:
                        ret.append([ws[r],i])
                    # right is center
                    if palind(r) and l in ws:
                        ret.append([i,ws[l]])
        return ret