最长回文子串

力扣 5. 最长回文子串

题目说明

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

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

示例

示例 1:

1
2
3

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

示例 2:

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

示例 3:

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

示例 4:

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

笔者理解

此题是一道字符串算法问题，在力扣题库中被定义为中等题。

解法

当笔者阅读完此题后，把回文看成中间的部分（类似ccc这样的子串）全是同一字符，左右部分相对称（abcccba）的字符串，让我们来看看具体如何实现的吧。

实现

class Solution {
    /*
     * 字符串
     * 切割
     */
    public String longestPalindrome(String s) {
        int n = s.length();

        // 保存答案始末位置
        int[] range = new int[2];
        char[] ch = s.toCharArray();
        for (int i = 0; i < n; i++) {

            // 把回文看成中间的部分全是同一字符，左右部分相对称
            // 找到下一个与当前字符不同的字符
            i = findLongest(ch, i, range);
        }
        return s.substring(range[0], range[1] + 1);
    }
    
    public static int findLongest(char[] ch, int low, int[] range) {
        int size = ch.length;

        // 上界
        int high = low;

        // 判断是否有类似于ccc这样的字符串
        while (high < size - 1 && ch[high + 1] == ch[low]) {
            high++;
        }

        // 定位中间全相等字符部分的最后一个字符
        int ans = high;

        // 从中间向左右扩散
        while (low > 0 && high < size - 1 && ch[low - 1] == ch[high + 1]) {
            low--;
            high++;
        }

        // 记录最大长度
        if (high - low > range[1] - range[0]) {
            range[0] = low;
            range[1] = high;
        }

        return ans;
    }
}