Skip to content

Latest commit

 

History

History
119 lines (66 loc) · 3.07 KB

0336._Palindrome_Pairs.md

File metadata and controls

119 lines (66 loc) · 3.07 KB
Raw

336. Palindrome Pairs

难度: Hard

刷题内容

原题连接

内容描述


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:

Input: ["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: ["bat","tab","cat"]
Output: [[0,1],[1,0]] 
Explanation: The palindromes are ["battab","tabbat"]

解题方案

思路 1 - 时间复杂度: O(N^2)- 空间复杂度: O(1)******

对于每一个word，我们只需要算出它的所有prefix和suffix，

比如‘abc’：
它的所有prefix为'', 'a', 'ab', 'abc'
它的所有suffix为'', 'c', 'cb', 'cba'

现在有两种情况：

  1. 如果前缀pref是回文且后缀suff的reverse也在words里面，那么suff[::-1]+(pref+suff)肯定是回文, 注意其中suff[::-1]不能等于word本身
  2. 如果后缀suff是回文且前缀pref的reverse也在words里面，那么(pref+suff)+pref[::-1]肯定是回文, 注意其中pref[::-1]不能等于word本身

但是！！！我们不要忘记直接这样算会有duplicates，例如:

输入为["abcd","dcba"]

直接按照上面的算法我们会返回[[0,1], [1,0], [0,1], [1,0]]

但实际上应该返回[[0,1], [1,0]]

那么究竟为什么会有重复呢？
因为前面验证第一种情况的时候计算了'abcd'+(''+'dcba')和'dcba'+(''+'abcd')的情况
后面验证第二种情况的时候我们又计算了('abcd'+'')+'dcba'和(‘dcba'+'')+'abcd'的情况

这就导致了重复，所以在计算第二种情况的时候我们要排除suffix就是word本身的情况

beats 89.80%

class Solution(object):
    def palindromePairs(self, words):
        """
        :type words: List[str]
        :rtype: List[List[int]]
        """
        lookup = {
            word: i for i, word in enumerate(words)
        }
        res = []
        for i, word in enumerate(words):
            for j in range(len(word)+1):
                pref, suff = word[:j], word[j:]
                # 如果后缀suff是回文且前缀pref的reverse也在words里面，那么(pref+suff)+pref[::-1]肯定是回文
                if suff == suff[::-1] and pref[::-1] in lookup and pref[::-1] != word:
                    res.append([i, lookup[pref[::-1]]])
                # 如果前缀pref是回文且后缀suff的reverse也在words里面，那么suff[::-1]+(pref+suff)肯定是回文
                if pref == pref[::-1] and suff[::-1] in lookup and suff[::-1] != word:
                    # 这是为了保证没有重复，例如：
                    # 如果前面算了'abcd'+(''+'dcba')和'dcba'+(''+'abcd')的情况
                    # 后面不能再算一遍('abcd'+'')+'dcba'和(‘dcba'+'')+'abcd'了
                    if j != 0:
                        res.append([lookup[suff[::-1]], i])
        return res