Hard

题目描述

给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。

返回通过执行此操作能找到的最短回文串。

示例 1：

输入：s = "aacecaaa"
输出："aaacecaaa"

示例 2：

输入：s = "abcd"
输出："dcbabcd"

提示：

  • 0 <= s.length <= 5 * 10^4
  • s 仅由小写英文字母组成

解题思路

解题思路

这道题要求在字符串前面添加最少的字符使其成为回文串。关键思路是找到从开头开始的最长回文前缀。

方法一：KMP算法（推荐）

构造字符串 s + "#" + reverse(s)，其中 # 是分隔符。然后使用KMP算法计算这个新字符串的最长前缀后缀匹配长度。这个长度就是原字符串 s 从开头开始的最长回文前缀的长度。

例如：s = "aacecaaa"

  • 构造："aacecaaa#aaacecaa"
  • KMP得到最长匹配长度为4，说明前4个字符"aace"构成最长回文前缀
  • 需要添加的字符数 = len(s) - 4 = 4

方法二：双指针暴力

从后往前尝试每个位置，检查从开头到该位置是否构成回文。时间复杂度较高但思路简单。

方法三：Rolling Hash

使用多项式哈希快速判断回文，效率较高但实现复杂。

KMP方法在时间复杂度和实现复杂度之间取得了很好的平衡，是最推荐的解法。

代码实现

class Solution {
public:
    string shortestPalindrome(string s) {
        if (s.empty()) return s;
        
        string rev = s;
        reverse(rev.begin(), rev.end());
        string combined = s + "#" + rev;
        
        vector<int> lps(combined.length(), 0);
        int len = 0;
        
        for (int i = 1; i < combined.length(); i++) {
            while (len > 0 && combined[i] != combined[len]) {
                len = lps[len - 1];
            }
            if (combined[i] == combined[len]) {
                len++;
            }
            lps[i] = len;
        }
        
        int palindromeLen = lps[combined.length() - 1];
        string prefix = rev.substr(0, s.length() - palindromeLen);
        
        return prefix + s;
    }
};

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        if not s:
            return s
        
        rev = s[::-1]
        combined = s + "#" + rev
        
        lps = [0] * len(combined)
        length = 0
        
        for i in range(1, len(combined)):
            while length > 0 and combined[i] != combined[length]:
                length = lps[length - 1]
            
            if combined[i] == combined[length]:
                length += 1
            
            lps[i] = length
        
        palindrome_len = lps[-1]
        prefix = rev[:len(s) - palindrome_len]
        
        return prefix + s

public class Solution {
    public string ShortestPalindrome(string s) {
        if (string.IsNullOrEmpty(s)) return s;
        
        string rev = new string(s.Reverse().ToArray());
        string combined = s + "#" + rev;
        
        int[] lps = new int[combined.Length];
        int len = 0;
        
        for (int i = 1; i < combined.Length; i++) {
            while (len > 0 && combined[i] != combined[len]) {
                len = lps[len - 1];
            }
            if (combined[i] == combined[len]) {
                len++;
            }
            lps[i] = len;
        }
        
        int palindromeLen = lps[combined.Length - 1];
        string prefix = rev.Substring(0, s.Length - palindromeLen);
        
        return prefix + s;
    }
}

var shortestPalindrome = function(s) {
    if (!s) return s;
    
    const rev = s.split('').reverse().join('');
    const combined = s + '#' + rev;
    
    const lps = new Array(combined.length).fill(0);
    let len = 0;
    
    for (let i = 1; i < combined.length; i++) {
        while (len > 0 && combined[i] !== combined[len]) {
            len = lps[len - 1];
        }
        if (combined[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度KMP算法
时间复杂度O(n)
空间复杂度O(n)

其中 n 为字符串 s 的长度。KMP算法只需要遍历一次构造的字符串，空间复杂度主要用于存储LPS数组和反转字符串。

相关题目