最长回文子串

1. 最长回文子串

标签：双指针 字符串 动态规划

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

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

示例 2：
输入：s = "cbbd"
输出："bb"

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

方案一：暴力解法,时间复杂度为 O(n^3),空间复杂度：O(1)

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        if (n == 1)
            return s;
        if (isPalindromic(s))
            return s;
        String temp = "";
        int tempMax = 0;
        String target = "";
        for (int x = 0; x <= n - 1; x++) {
            for (int y = x + 1; y <= n; y++) {
                temp = s.substring(x, y);
                if (isPalindromic(temp) && temp.length() > tempMax) {
                    target = temp;
                    tempMax = temp.length();
                }
            }
        }
        return target;
    }

    public boolean isPalindromic(String s) {
        int n = s.length();
        for (int i = 0; i < n / 2; i++) {
            if (s.charAt(i) != s.charAt(n - i - 1)) {
                return false;
            }
        }
        return true;
    }
}

方案二：动态规划

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1)
            return "";
        // 回文子串的起始和结束索引
        int start = 0, end = 0; 
        boolean[][] dp = new boolean[s.length()][s.length()];

        // 初始化单个字符的回文
        for (int i = 0; i < s.length(); i++) {
            dp[i][i] = true;
        }

        // 填充 dp 数组
        for (int len = 2; len <= s.length(); len++) {
            for (int i = 0; i <= s.length() - len; i++) {
                int j = i + len - 1;
                if (s.charAt(i) == s.charAt(j) && (len < 3 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                    if (len > end - start) {
                        start = i;
                        end = j;
                    }
                }
            }
        }

        // 返回最长的回文子串
        return s.substring(start, end + 1);
    }