字符串 - 最长回文子串

5. 最长回文子串

题目描述

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：
输入: "cbbd"
输出: "bb"

算法思想

解法一：暴力算法
暴力算法应该是本题的最基础解法了，基本思路是这样的：判断以索引位置i (0 <= i < len)为起始位置，长度分别为 j (2 <= j <= len - i) 的子串是否为回文串，同时使用变量startIndex来记录最长回文子串的起始位置，maxLength来记录最长回文子串的长度。

---

解法二：动态规划
遇到最值问题，我们一般都会往贪心或者动态规划上靠拢。显然，这一题可以采用动态规划来实现，但是，对于动态规划的问题，我们脑海中能很快的浮现出解题 “三部曲”：
1）定义状态
2）根据定义的状态写出状态转移方程
3）考虑边界

而在这“三部曲”中最难的就是第一步，即如何定义状态？，如果根据定义的状态很难写出状态转移方程，那么就要考虑状态定义的是否正确。

针对本题而言：
1）定义状态：dp[i][j]用来表示子串s[i, j]是否为回文串，这里的子串s[i, j]为闭区间，且有i < j
2）状态转移方程：如果子串s[i, j]是回文串，那么子串s[i+1, j-1]必然也是回文子串，因此，状态转移方程
dp[i][j] = dp[i+1][j-1] && s[i] == s[j]
3）考虑边界：此题的边界为s[i+1, j-1]不会构成一个闭区间，即s[i+1, j-1]的长度小于2，即(j-1) - (i+1) +1 < 2，得到j - i < 3 。
在j - i < 3 的前提下，如果s[i] == s[j] 且 s[i+1, j-1]为空串或者只包含1个字符，则直接判断s[i ... j]为回文串。

代码实现

解法一：暴力算法

class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        if (len <= 2) {
            return s;
        }
        int startIndex = 0;
        int maxLength = 1;
        for (int i = 0; i < len; i++) {
            // 如果以i起始位置一直到原字符串结尾的子串，其长度小于maxLength，说明该子串肯定不会包含最长回文子串
            for (int j = 2; j <= len - i && maxLength < len -i; j++) {
                String substr = s.substring(i, i + j);
                // 如果以i起始位置，长度为j的子串是回文串，且长度大于maxLength，则更新起始位置startIndex和maxLength
                if (isPalindrome(substr) && substr.length() > maxLength) {
                    startIndex = i;
                    maxLength = j;
                }
            }
        }

        return s.substring(startIndex, startIndex + maxLength);
    }

    /**
    * 判断一个字符串是否为回文串
    **/
    public static boolean isPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left ++;
            right --;
        }
        return true;
    }
}

算法的时间复杂度为O(n^3)，空间复杂度为O(1)

---

解法二：动态规划

class Solution {
    public static String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }

        // dp[i][j]用来存储子串s[i...j]是否为回文串
        boolean[][] dp = new boolean[len][len];
        for (int i = 0; i < len ; i++) {
            Arrays.fill(dp[i], true);
        }
        int startIndex = 0;
        int maxLength = 1;

        for (int j = 1; j < len; j++) {
            for (int i = 0; i < j; i++) {
                if (s.charAt(i) != s.charAt(j)) {
                    dp[i][j] = false;
                } else {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }

                if (dp[i][j] && j - i + 1 > maxLength) {
                    maxLength = j - i + 1;
                    startIndex = i;
                }
            }
        }

        return s.substring(startIndex, startIndex + maxLength);
    }
}

时间复杂度为O(n^2)
空间复杂度为O(n^2)，即dp问题一般都是采用空间来换时间。