🥇336回文对@

🥇Hard

给定一组 互不相同 的单词， 找出所有不同 的索引对(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"]

题解

暴力

最最一般的解法，就是暴力，枚举每一对字符串的组合，暴力判断它们是否能够构成回文串即可。也是我想到的方法。
但这样复杂度太高，时间复杂度为，其中 n 是字符串的数量，m 是字符串的平均长度。

Python

def judge(word):
    left = 0
    right = len(word) - 1
    while left < right:
        if word[left] == word[right]:
            left += 1
            right -= 1
        else:
            return False
    return True


def palindromePairs(words):
    result = []
    for i in range(len(words) - 1):
        for j in range(1, len(words)):
            ans = words[i] + words[j]
            if judge(ans):
                result.append([i, j])
            ans1 = words[j] + words[i]
            if judge(ans1):
                result.append([j, i])
    re = []
    for res in result:
        if res not in re:
            re.append(res)

    return re


a = ["abcd", "dcba", "lls", "s", "sssll"]
b=["bat","tab","cat"]

print(palindromePairs(b))

可以对其进行优化。

枚举前缀和后缀

思路

假设两个字符串s1和s2，s1+s2是一个回文串，记两个字符串长度分别是len1和len2，有一下三种情况：

1. len1=len2，这种情况下s1是s2的翻转
2. len1>len2，这种情况可以把s1拆分成t1和t2两部分，其中t1是s2的翻转，t2是一个回文串
3. len1<len2，这种情况可以把s2拆分成t1和t2两部分，其中t2是s1的翻转，t1是一个回文串

这样的话，对于每一个字符串，令其为s1和s2中较长的一个，然后找到可能和它构成回文串的字符即可。

也就是说，枚举每一个字符串k，令其为s1和s2中较长的一个，那么k可以拆分成两部分t1和t2。

1. 当t1是回文串时，符合情况3，只需要查询给定的字符串序列是否包含t2的翻转
2. 当t2是回文串时，符合情况2，只需查询给定的字符串序列是否包含t1的翻转

所以需要枚举字符串k的每一个前缀和后缀，判断是否为回文串，如果是回文串，就查询其剩余剩余部分的翻转是否在给定字符串序列中出现即可。