leetcode 005 最长回文子串

题目

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

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

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

示例 2：

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

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

思路

中心扩散法

中心扩散法，依次把字符串中每个字符当成中心，向左右扩散比对。将某个字符最大的扩散长度和开始长度记录下来，最后返回这个最大的扩散区间即可。

详细规则如下：

1. 循环 s 中每个字符作为中心，这个字符的下标定义为 i
2. 扩散初始状态
   1. 向左扩散 left = i - 1
   2. 向右扩展 right = i + 1
   3. len = 1 表示扩散长度默认为 1 (最少的回文字符就是 1，随便一个字符都可以认为是一个回文字符)
   4. maxLen 表示最大的扩散宽度，可能从下标 3 向两边扩散了 3 次，但从下标 5 可以向左右扩散6 次，所以要记录最大的扩散宽度。
   5. maxStartIndex 因为这道题不是让计算最大扩散宽度，还要返回整个回文字母，所以还要记录最大扩散的 left 值，是回文字符串的开始值。
3. 最后返回 s.substring(maxStartIndex + 1, maxStartIndex + maxLen + 1)。之所以要 +1 是因为 maxStartIndex 这个索引已经不包含回文字符了，它是回文字符的左边的那个索引。

动态规划

使用 dp[l][r] 表示从 l 到 r 这段是否是回文，如果 dp[l][r] = true，那么要判断 dp[l - 1][r + 1] 时，只需要判断 l - 1 和 r + 1 这两个位置的字符串是否是相等的即可。 例如 str = "cabac"，l = 1，r = 3，dp[1][3] 确定了是回文串时，只需要判断左右两个的 l - 1 = 0 与 r + 1 = 4 这两个位置的字符串是否相等。（大白话就是如果一个字符串是回文串，那么在其左右两个加一个相同的字符，那它还是回文串）。

状态转移方程，dp[l][r]=true 并且(l-1)和（r+1)两个位置为相同的字符，此时 dp[l-1][r+1]=true。

代码

中心扩散法

class Solution {  
    public String longestPalindrome(String s) {  
        int strLength = s.length();  
        int left = 0;  
        int right = 0;  
  
        int len = 1;  
        int maxStartIdx = 0;  
        int maxLen = 0;  
  
        for (int i = 0; i < strLength; i++) {  
            left = i - 1;  
            right = i + 1;  
            while (left >= 0 && s.charAt(left) == s.charAt(i)) {  
                left--;  
                len++;  
            }  
            while (right < strLength && s.charAt(right) == s.charAt(i)) {  
                right++;  
                len++;  
            }  
  
            while (left >= 0 && right < strLength && s.charAt(left) == s.charAt(right)) {  
                left--;  
                right++;  
                len += 2;  
            }  
  
            if (len > maxLen) {  
                maxLen = len;  
                maxStartIdx = left;  
            }  
            len = 1;  
        }  
  
        return s.substring(maxStartIdx + 1, maxStartIdx + maxLen + 1);  
    }  
}

动态规划

class Solution {
    public String longestPalindrome(String s) {
        int strLen = s.length();
        int maxStart = 0;  // 最长回文串的起点
        int maxEnd = 0;    // 最长回文串的终点
        int maxLen = 1;    // 最长回文串的长度

        boolean[][] dp = new boolean[strLen][strLen];

        for (int r = 1; r < strLen; r++) {
            for (int l = 0; l < r; l++) {
                // 1. s.charAt(l) == s.charAt(r) 表示当前 left 和 right 相等
                // 2. dp[l + 1][r - 1] 如果回文字符串左右加上两个一样的字符，那它还是个回文字符串.
                //    如 aba，左右各加一个 c，那它还是回文字符串，这里的左右各加一个 c 其实就是第一个判断
                // 3. r - l <= 2 表示如果的间距小于等于 2，就不用判断 l 和 r 之间的那个子字符串是否是回文字符串了
                //    如 daac, l = 1, r = 2 时，条件 1 满足，但 r - l 为 1，这时候就不用判断条件 2 了，因为没有更小的子串了
                //       0123
                //    如 dabac, l = 1, r = 3 时，条件 1 满足，但 r - l 为 2，这时候也不用判断条件 2，因为 dp[l + 1][r - 1] 其实判断的是同一个字符(在这里 l  = 1, r = 3, l + 1 = 2, r - 1 = 2). 肯定会相等也不用判断.
                //       01234
                if (s.charAt(l) == s.charAt(r) && (dp[l + 1][r - 1] || r - l <= 2)) {
                    dp[l][r] = true;
                    if (r - l + 1 > maxLen) {
                        maxStart = l;
                        maxEnd = r;
                        maxLen = r - l + 1;
                    }
                }
            }
        }

        return s.substring(maxStart, maxEnd + 1);
    }
}