将字符串转换为回文

Question

给定字符串s，我们可以在开头添加字符。任务是在执行尽可能少的操作的同时将s变成回文。

1<=|s|<=10^5

def make_palindrome(s):
    if s == s[::-1]:
        return s  # If the string is already a palindrome, return it
        
    
    for i in range(len(s),0, -1):
        if s[:i] == s[:i][::-1]:
            return s[i:][::-1] + s

这是我的代码，它通过了大多数情况，但对于某些情况，我超出了时间限制，超过 2 秒。可以帮忙优化一下吗？

例如。 abcd -> dcbabcd aabc -> cbaabc 皮划艇 -> 皮划艇

Answer 1

想象一根绳子：

“阿巴德法格”

您想在开头添加字符以使其成为回文。 添加的字符来自原始字符串的末尾，所以我们有：

GAFED + ABBA + DEFAG

所以你的问题变成了：我必须从原始字符串的末尾删除多少字符，这样我才能以回文

ABBA

或空字符串结尾？

我们有

ABBADEFAG

，所以我们取第一个字符 A 并从字符串末尾开始查找出现的情况，然后我们找到 A

阿巴德夫 A G

现在下一个是B，所以前一个一定是B，但不是，是F。所以我们跳过找到的A，继续寻找A

ABB DEFAG

现在下一个字符必须是 B -> 是 我们得到两个索引，找到彼此，所以我们找到了回文

阿巴

现在我们只需反转字符串的其余部分并将其附加到开头即可。

GAFED + ABBA + DEFAG