336. 回文对 [hard]

https://leetcode-cn.com/problems/palindrome-pairs/

给定一组唯一的单词，找出所有不同的索引对(i, j)，使得列表中的两个单词， words[i] + words[j] ，可拼接成回文串。

示例 1:

输入: ["abcd","dcba","lls","s","sssll"]
输出: [[0,1],[1,0],[3,2],[2,4]] 
解释: 可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]

示例 2:

输入: ["bat","tab","cat"]
输出: [[0,1],[1,0]] 
解释: 可拼接成的回文串为 ["battab","tabbat"]

通过次数8,149 | 提交次数22,297

First Try

2020-08-06

暴力法O(N^2)果然无法通过，这个是O(N*W), 看题解才了解到的。

对于两个拼接的字符，长度字符肯定在边界处有一个小回文，要么是左侧要么是右侧，去除回文后剩下的部分取反，看是否在字符串列表里，如果存在就能够凑一起。对于两个同样长度的字符，则可以考虑空字符串也是回文，这样就能把两个相等的字符串凑起来。

容易出错的一是需要注意左侧和右侧都需要考虑到；二是对于["a", ""]这种测试样例，需要考虑到在左侧和右侧都能够贴上空字符串，因此需要用range(len(word) + 1) 而不是range(len(word)); 其三是去重重复，但那么多小细节真的不如直接在结果里进行去重。

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        """
        bug test:
        ["abcd","dcba"]
        ["a", ""]
        """
        cache = dict()
        for idx, word in enumerate(words):
            cache[word] = idx 

        rv = [ ]
        # 只考虑较长的字符串，必有沿着中间合并处的部分字符为回文；如果字符串相等，自空字符串为回文，并不影响
        for i, word in enumerate(words):
            # 考虑到左侧空字符串和右侧空字符串的两种情况，需要len(word) + 1
            # 不然在考虑右边部分为回文的时候，不会出现回文为空；反之考虑左边部分为回文，则可以出现回文为空的情况。 太麻烦了。

            for widx in range(len(word) + 1): 
                # print(widx, word[:widx], word[widx:])
                # 右边部分为回文
                if word[widx:] == word[widx:][::-1] and word[:widx][::-1] in cache:
                    j = cache[word[:widx][::-1]]
                    if j != i:
                        rv.append([i, j])
                # 左边部分为回文
                # 这个widx不允许为0存粹为了去重，但综合起来考虑的细节太多了，还不如最终统一在答案列表里去重来得干脆
                if widx and word[:widx] == word[:widx][::-1] and word[widx:][::-1] in cache: 
                    j = cache[word[widx:][::-1]]
                    if j != i:
                        rv.append([j, i])
        return rv 

执行用时：872 ms, 在所有 Python3 提交中击败了29.68%的用户
内存消耗：14.8 MB, 在所有 Python3 提交中击败了89.29%的用户

Time Exceeded Try

2020-08-06

暴力法优化版

以为暴力法一不通过是因为使用字符串拼接了，尝试用了非字符串拼接的回文测试，结果速度竟然更慢了。

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        # 以为不用字符串拼接算优化，结果速度更慢
        print(len(words))

        def fast_palindrome(wi, wii):
            li, lii = len(wi), len(wii)
            lft, rt = 0, li + lii - 1
            idx_chr = lambda idx: wi[idx] if idx <= li - 1 else wii[idx - li] # 写成了wii[idx - (li - 1)]
            while lft < rt:
                if idx_chr(lft) != idx_chr(rt):
                    return False 
                lft += 1
                rt -= 1
            return True 

        rv = []
        for i in range(len(words) - 1):
            for j in range(i + 1, len(words)):
                if fast_palindrome(words[i], words[j]):
                    rv.append([i, j])
                if fast_palindrome(words[j], words[i]):
                    rv.append([j, i])
        return rv

朴素的暴力法，在最长字符串要耗费3s

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        # O(N2)算法可能不太行啊, 果然超时了, 4k单词耗时3s
        print(len(words))


        rv = []
        for i in range(len(words) - 1):
            for j in range(i + 1, len(words)):
                if words[i][0] != words[j][-1] and words[i][-1] != words[j][0]:
                    continue 
                wi = words[i] + words[j]
                wii = words[j] + words[i]
                if wi == wi[::-1]:
                    rv.append([i, j])
                if wii == wii[::-1]:
                    rv.append([j, i])
        return rv

336. 回文对 [hard]​

First Try​

Time Exceeded Try​

336. 回文对 [hard]

First Try

Time Exceeded Try