LeetCode 214. 最短回文串

Categories:

题目描述
思路分析
1. 解法一：KMP 前缀函数（推荐）
相似题目

题目描述

✅ 214. 最短回文串

思路分析

解法一：KMP 前缀函数（推荐）

核心思路：

设 rev 为 s 的反转，构造 t = s + "#" + rev。

t 的最长相等前后缀长度即为 s 的最长回文前缀长度。

将剩余后缀反转后拼到前面即可。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字符串长度。

空间复杂度：O(n)，用于前缀函数数组。

class Solution {
    public String shortestPalindrome(String s) {
        String rev = new StringBuilder(s).reverse().toString();
        String t = s + "#" + rev;

        int[] lps = new int[t.length()];
        for (int i = 1; i < t.length(); i++) {
            int j = lps[i - 1];
            while (j > 0 && t.charAt(i) != t.charAt(j)) {
                j = lps[j - 1];
            }
            if (t.charAt(i) == t.charAt(j)) {
                j++;
            }
            lps[i] = j;
        }

        int keep = lps[t.length() - 1];
        String add = rev.substring(0, s.length() - keep);
        return add + s;
    }
}

func shortestPalindrome(s string) string {
    rev := reverseString(s)
    t := s + "#" + rev

    lps := make([]int, len(t))
    for i := 1; i < len(t); i++ {
        j := lps[i-1]
        for j > 0 && t[i] != t[j] {
            j = lps[j-1]
        }
        if t[i] == t[j] {
            j++
        }
        lps[i] = j
    }

    keep := lps[len(t)-1]
    add := rev[:len(s)-keep]
    return add + s
}

func reverseString(s string) string {
    b := []byte(s)
    for l, r := 0, len(b)-1; l < r; l, r = l+1, r-1 {
        b[l], b[r] = b[r], b[l]
    }
    return string(b)
}

相似题目

题目	难度	考察点
5. 最长回文子串	中等	回文、双指针
131. 分割回文串	中等	回溯、DP
132. 分割回文串 II	困难	动态规划
647. 回文子串	中等	DP、中心扩展
336. 回文对	困难	哈希表

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/66613602