题目描述

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

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

示例 1：

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

示例 2：

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

提示：

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

题解

暴力解法

枚举所有子串

    public String longestPalindrome(String s) {
        int max = 0;
        String res = "";
        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                String sub = s.substring(i, j + 1);
                if (checkPalindrome(sub) && sub.length() > max) {
                    max = sub.length();
                    res = sub;
                }
            }
        }
        return res;
    }
    public boolean checkPalindrome(String s) {
        int l = 0, r = s.length() - 1;
        while (l < r) {
            if (s.charAt(l) != s.charAt(r)) {
                return false;
            }
            else {
                l++;
                r--;
            }
        }
        return true;
    }

• 时间复杂度：O(n³)
• 空间复杂度：O(1)

正常解法1

枚举所有位置，以该位置作为中心从中间不断向两边扩展，依次判断，同时字符串长度为奇数和偶数的情况

    public String longestPalindrome(String s) {
        String res = "";
        int max = 0;
        for (int i = 0; i < s.length(); i++) {
            String str1 = findLongestStr(s, i, i);
            String str2 = findLongestStr(s, i, i + 1);
            if (Math.max(str1.length(), str2.length()) > max) {
                max = Math.max(str1.length(), str2.length());
                res = str1.length() > str2.length() ? str1 : str2;
            }
        }
        return res;
    }
    public String findLongestStr(String s, int l, int r) {
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            l--;
            r++;
        }
        return s.substring(l + 1, r);
    }

• 时间复杂度：O(n²)
• 空间复杂度：O(1)

正常解法2

一个回文子串，去掉两端后剩下的字符串也一定是子串，abcba -> bcb -> c，因此可以利用该状态转移方程使用动态规划，且单字符串一定为回文子串，双字符串直接比较，初始化完成后，用二维数组dp[i,j]表示s(i,j)是否为回文子串，如果是，那么dp[i-1,j+1]则只需判断s(i-1)和s(j+1)这两个字符是否相等

public String longestPalindrome(String s) {
        boolean[][] dp = new boolean[s.length()][s.length()];
        int start = 0, end = 0;
        int max = 0;
        for (int i = 0; i < s.length(); i++) {
            dp[i][i] = true;
        }
        for (int i = s.length() - 1; i >= 0; i--) {
            for (int j = i + 1; j < s.length(); j++) {
                if (j - i <= 2) {
                    dp[i][j] = s.charAt(i) == s.charAt(j);
                }
                else {
                    dp[i][j] = dp[i + 1][j - 1] && s.charAt(i) == s.charAt(j);
                }
                if (dp[i][j] && j - i + 1 > max) {
                    max = j - i + 1;
                    start = i;
                    end = j;
                }
            }
        }
        return s.substring(start, end + 1);
    }