题目描述

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

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母（大写和/或小写）组成

解题思路

官方题解链接

代码(动态规划)

public String longestPalindrome(String s) {
        if (s.length() < 2) {
            return s;
        }
        int len = s.length();
        //dp[i][j]: 索引i-j的字符串是否是一个回文串
        boolean[][] dp = new boolean[len][len];
        for (int i = 0; i < len; i++) {
            //dp[i][i]:单个字符都属于回文串
            dp[i][i] = true;
        }
        //保存最大的回文串的左边界
        int begin = 0;
        //保存最大的回文串的长度
        int maxLength = 1;
        //chars:字符串转成字符数组
        char[] chars = s.toCharArray();

        //L:字符串长度
        for (int L = 2; L <= len; L++) {
            //i:左边界索引
            for (int i = 0; i < len; i++) {
                //j:右边界索引
                int j = i + L - 1;
                //越界终止
                if (j >= len) {
                    break;
                }

                if (chars[i] == chars[j]) {
                    //i:j的字符串长度小于3,则dp[i][j] = true,否则dp[i][j] = dp[i+1][j-1];
                    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;
                    begin = i;
                }
            }
        }
        //截取最大回文子串
        return s.substring(begin,begin + maxLength);
    }

复杂度

时间复杂度: O(n^2)
空间复杂度: O(n^2)

代码(中心扩展算法)

public String longestPalindrome(String s) {
        if (s.length() < 1) {
            return "";
        }
        int size = s.length();
        //start:最长回文串左边界
        int start = 0;
        //end:最长回文串右边界
        int end = 0;
        for (int i = 0; i < size; i++) {
            int len1 = expand(s, i, i);
            int len2 = expand(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start + 1) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return  s.substring(start, end + 1);
    }

    int expand(String str, int left, int right) {
        while (left >= 0 && right < str.length() && str.charAt(left) == str.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }