想要精通算法和SQL的成长之路 - 最长回文子串

前言

想要精通算法和SQL的成长之路 - 系列导航

一. 最长回文子串

原题链接

1.1 中心扩散法的运用

这类具有回文性质的题目，我们如果用常规的从左往右或者从右往左的遍历方式，在编码上往往比较麻烦。那不妨，我们以字符串中的每一个字符为起点，同时向左右扩散，判断左右的字符是否相等，即中心扩散法，往往这样更加通俗易懂。编码实现上也更为简单。

1. 我们从左往右遍历字符串，将每个字符串 s(i) 视为中心，分别向左右扩散。
2. 先向左扩散，排除掉和中心字符 s(i) 相同字符。判断条件：s(left) == s(i)。
3. 先向右扩散，排除掉和中心字符 s(i) 相同字符。判断条件：s(right) == s(i)。
4. 再同时向左右扩散，判断条件：s(left) == s(right)

public class Test5 {
    public String longestPalindrome(String s) {
    	// 最长回文子串的起始位置
        int maxStart = 0;
        // 左右指针，以及数组长度。maxLen：最长回文子串长度，curLen：当前的回文子串长度
        int left, right, len = s.length(), maxLen = 0, curLen = 1;
        for (int i = 0; i < len; i++) {
            left = i - 1;
            right = i + 1;
            // 向左扩散，去重
            while (left >= 0 && s.charAt(left) == s.charAt(i)) {
                left--;
                curLen++;
            }
            // 向右扩散，去重
            while (right < len && s.charAt(right) == s.charAt(i)) {
                right++;
                curLen++;
            }
            // 同时向左右扩散
            while (left >= 0 && right < len && s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
                curLen += 2;
            }
            // 更新最长回文子串长度和起始位置
            if (curLen > maxLen) {
                maxLen = curLen;
                maxStart = left;
            }
            curLen = 1;
        }
        // 截取字符串， 最长回文子串起始位置 ~ 起始位置+长度
        return s.substring(maxStart + 1, maxStart + maxLen + 1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36