最长回文字符串

题目信息

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

示例 3：

输入：s = "ac"
输出："a"

解题思路

1. 暴力破解：
   1. 穷举出所有子串，时间复杂度O(n^3)，空间复杂度O(1)
   2. 从最长子串依次判断是否满足回文
2. 无效操作分析：
   1. 长度为1的子串一定满足回文，“a”
   2. 长度为2的子串，只有两个元素相同时，满足回文，“aa”
   3. 长度2以上奇数时，除最中间的元素外，其余元素首尾可对应消除，“abcba”
   4. 长度2以上偶数时，元素首尾可对应消除，“abba”
3. 优化方法：动态规划
   1. 找状态：dp[i][j] 长度i到j的子串是否满足回文
   2. 状态转移方程：dp[i][j] = dp[i+1][j-1] 满足条件
   3. 终止条件：j - 1 - (i + 1) + 1 < 2, 即: j - i < 3
   4. 启示状态（初始化）：dp[i][i] 长度为1的子串一定回文
4. 考虑边界：字符串为null和字符串为空字符串
5. 编码实现：时间复杂度：O(n^2)，空间复杂度O(1)

代码

class Solution {
    public String longestPalindrome(String s) {
        // 处理异常情况
        if (s == null) {
            return "";
        }
        // 处理空字符串和长度为1的字符串
        int len = s.trim().length();
        if (len <= 1) {
            return s;
        }

        // 记录最大长度和起始位置
        int maxLen = 1;
        int begin = 0;
        // dp[i][j]表示s[i..j]是回文串
        boolean[][] dp = new boolean[len][len];
        // 初始化
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }

        char[] charArr = s.toCharArray();
        // 分析：dp[i][j] = dp[i+1][j-1]，即当前状态与表格左下角的状态直接相关
        for (int j = 1; j < len; j++) {
            for (int i = 0; i < j; i++) {
                if (charArr[i] != charArr[j]) {
                    dp[i][j] = false;
                } else {
                    // 终止条件：字符串长度需要严格满足长度大于2
                    // j - 1 - (i + 1) + 1 < 2, 即: j - i < 3
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                // 更新最长回文子串的记录
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        // 截取子串并返回
        return s.substring(begin, begin + maxLen);
    }
}

Manacher 算法（了解）
原字符串预处理 + 动态规划 + 中心扩散
(预处理字符串的回文子串长度 - 1) / 2 = 原始字符串的回文子串的长度 = 以 i 为中心向两边能扩散的步数

核心逻辑：

// 状态转移方程
int mirror = 2 * center - i;
p[i] = min(maxRight - i, p[mirror])
// 尝试中心扩散，更新p[i]的值
int left = i - (1 + p[i]);
int right = i + (1 + p[i]);
while(left >= 0 && right < sLen && charArr[left] == charArr[right]) {
    p[i]++;
    left--;
    right++;
}

https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/

时间复杂度：O(n)，其中 n 是字符串的长度。由于对于每个位置，扩展要么从当前的最右侧臂长 right 开始，要么只会进行一步，而 right 最多向前走 O(n) 步，因此算法的复杂度为 O(n)。
空间复杂度：O(n)，我们需要 O(n)的空间记录每个位置的臂长。

题目来源：力扣（LeetCode）
题目链接：https://leetcode-cn.com/problems/longest-palindromic-substring

商业转载请联系官方授权，非商业转载请注明出处。