[Leetcode] 336. Palindrome Pairs

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

Example 1:
Given words = ["bat", "tab", "cat"]
Return [[0, 1], [1, 0]]
The palindromes are ["battab", "tabbat"]

Example 2:
Given words = ["abcd", "dcba", "lls", "s", "sssll"]
Return [[0, 1], [1, 0], [3, 2], [2, 4]]
The palindromes are ["dcbaabcd", "abcddcba", "slls", "llssssll"]

这道题的思路就是把每个word和index存到diction里面, 然后针对每个word, for loop, 拆分为两部分, 如果前面部分是palindrome, 那么把后面部分的单词reverse, 如果reverse后的单词在diction里面, ans.append(d[back], index); 同理, 如果后面部分是palindrome, 把前面部分的单词reverse, 如果reverse后的单词在diction里面, ans.append(index, d[back]). 此时需要注意的是在后面check的时候就不要考虑整个单词reverse的情况, 因为前面单词reverse的时候已经考虑到了. 如果不明白的话就用set去去重, 最保险的做法.

参考Solution.

class Solution(object):

    def palindromePairs(self, words):

        """

        :type words: List[str]

        :rtype: List[List[int]]

        """

        def checkpal(w):

            return w == w[::-1]  # 反正O(n), 所以用最粗暴的方式

        d, ans = {w:index for index, w in enumerate(words)},[]

        for word, index in d.items():

            l = len(word)

            for i in range(l+1): # l+1 因为pref要到[:l]

                pref = word[:i]

                suf = word[i:]

                if checkpal(pref):

                    back = suf[::-1]

                    if back != word and back in d:

                        ans.append([d[back], index])

                if i != l and checkpal(suf): # delete the duplicates

                    back = pref[::-1]

                    if back != word and back in d:

                        ans.append([index, d[back]])

        return ans

巴特西

[Leetcode] 336. Palindrome Pairs_Hard

最新文章

热门文章