5. 最长回文子串

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

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

示例 1：

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

示例 2：

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

提示：

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

解题思路

暴力法胡乱分析一通...

代码

/**
 * 5. 最长回文子串
 * 242ms 43MB
 *
 * @author mjz
 * @date 2023/5/14
 */
class Solution {
    public static String longestPalindrome(String s) {
        String result = s.isEmpty() ? s : s.substring(0, 1);
        int s_length = s.length();
        for (int i = 0; i < s_length; i++) {
            int low = i, high = s_length - 1;
            while (high > low) {

                // 可能的长度比当前的小，直接结束
                if (result.length() + i + 1 > s_length) {
                    // System.out.println("可能的长度比当前的小，直接结束 " + (s_length - i - 1));
                    return result;
                }

                while (high > low && s.charAt(high) != s.charAt(low)) {
                    high--;
                }

                int length = high - low + 1;
                if (length <= 0) {
                    break;
                }

                String substring = s.substring(i, i + length);
                // 可能的长度小于result才尝试判断
                boolean palindrome = isPalindrome(s, i, i + length - 1);
                if (palindrome) {
                    // System.out.println("result.length() < length = " + (result.length() < length));
                    if (result.length() < length) {
                        // System.out.println("找到回文：" + substring);
                        result = substring;
                    }
                    // 找到后肯定是当前这一轮的最大值，直接进入下一轮
                    break;
                } else {
                    high--;
                }
            }
        }
        return result;
    }

    public static boolean isPalindrome(String string, int startIndex, int endIndex) {
        while (endIndex >= startIndex && string.charAt(startIndex) == string.charAt(endIndex)) {
            startIndex++;
            endIndex--;
        }
        return endIndex <= startIndex;
    }
}
​