题目描述

给你一个字符串s，找到s中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

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

示例 2：

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

提示：

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

题目链接：https://leetcode.cn/problems/longest-palindromic-substring/

『1』暴力解法

解题思路：

先使用双重循环，依次枚举字符串s中以各字符为起始的子串，再通过 while 循环判断其是否为回文串，若是则记录其长度，以此过程来获得最长回文子串的长度。

实现代码：

class Solution {
    // Brute Force
    // n is the length of s
    // Time Complexity: O(n^3)
    // Space Complexity: O(1)
    public String longestPalindrome(String s) {
        if (s == null || s.isEmpty()) return "";

        // 与 char 数组相比，s.charAt(i) 会进行数组下标越界等检查，因此转为 char 数组会更高效
        // 使用 String：176ms
        // 转为 char[]：85ms
        char[] arr = s.toCharArray();
        int start = 0, end = 0;
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                // 做了优化，即先将截取字符串的长度与当前结果的长度进行比较，若大于再进行回文串的判断
                if (j - i + 1 > end - start + 1 && isPalindrome(arr, i, j)) {
                    start = i;
                    end = j;
                }
            }
        }
        // 注意 substring() 方法是左闭右开，因此 end 加1
        return s.substring(start, end + 1);
    }

    private boolean isPalindrome(char[] arr, int left, int right) {
        while (left < right) {
            if (arr[left] != arr[right]) return false;
            ++left;
            --right;
        }
        return true;
    }
}

『2』中心扩散法

解题思路：

首先根据回文串的定义，如果一个字符串正着读和反着读是一样的，那它就是回文串。
因此，回文可以从其中心展开。回文串在长度为奇数和偶数的时候，回文串中心的形态不同：中心为一个或两个元素。
对于长度为n的字符串，一个元素为中心的情况有n个，两个元素为中心的情况有n-1个，所以要对这两种情况都做遍历，也就是n + (n - 1) = 2n - 1次，时间复杂度为O(n)。
又由于每个回文中心最多会向外扩展O(n)次，因此时间复杂度为O(n^2)。

实现代码：

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.isEmpty()) return "";

        // 使用 String：6ms
        // 转为 char[]：16ms
        char[] arr = s.toCharArray();
        int start = 0, end = 0;

        for (int i = 0; i < arr.length - 1; i++) {
            int oddLen = expandAroundCenter(arr, i - 1, i + 1);
            int evenLen = expandAroundCenter(arr, i, i + 1);
            int len = Math.max(oddLen, evenLen);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    private int expandAroundCenter(char[] arr, int left, int right) {
        while (left >= 0 && right < arr.length && arr[left] == arr[right]) {
            --left;
            ++right;
        }
        // left 和 right 最后多加了一次
        return right - left - 1;
    }
}

『3』动态规划

解题思路：

如果字符串是回文串，两边分别增加一个相同字符，其仍然是回文串；两边分别增加一个不同字符，则其不是回文串。
因此一个字符串是不是回文串，取决于两边的字符是否相同、中间的字符串是不是回文串。
当两边字符相同且字符串长度小于4时，该字符串一定是回文串。
参考视频：使用【动态规划】求解最长回文子串

实现代码：

class Solution {
    // Dynamic Programming
    // n is the length of s
    // Time Complexity: O(n^2)
    // Space Complexity: O(n^2)
    public String longestPalindrome(String s) {
        if (s == null || s.isEmpty()) return "";

        int n = s.length();
        // 字符串 s[i...j] 是否为回文串
        boolean[][] dp = new boolean[n][n];
        for (int i = 0; i < n; i++) dp[i][i] = true;
        for (int j = 1; j < n; j++) {
            for (int i = 0; i < j; i++) {
                if (s.charAt(i) != s.charAt(j)) {
                    dp[i][j] = false;
                } else {
                    dp[i][j] = j - i < 3 || dp[i + 1][j - 1];
                }
            }
        }
        int start = 0, end = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (j - i + 1 > end - start + 1 && dp[i][j]) {
                    start = i;
                    end = j;
                }
            }
        }
        return s.substring(start, end + 1);
    }
}