最长回文子串

题目:

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

示例 1：

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

示例 2：

输入：s = “cbbd”
输出：“bb”

思路:中心扩散法
len=1,len是当前循环里最长回文子串的长度,maxLen是最长回文子串长度
(maxStart+1)是最长回文子串的首元素下标,后面会解释.

1.开始时left指向i的左侧元素,right指向i的右侧元素
left=i-1;right=i+1;
2.先判断left位置的元素和i位置的元素是否相等,如果相等,len++,毕竟两个相等的字符也是回文串,所以len++,然后left左移一位,left--
3…再判断left位置的元素和i位置的元素是否相等,如果相等,len++,毕竟两个相等的字符也是回文串,所以len++,然后right右移一位,right++
4.然后看left位置元素和right位置元素是否相同,如果相同
则len+=2,left--,right++,这时的left–和right++就相当于从i出开始向外扩散.去查找回文字符串.
5.将此时的len与maxLen作比较,如果len>maxLen,则将len的值赋给maxLen,始终让maxLen的值为最大的,也就是最长回文子串的长度,然后将此时left的值赋给maxStart,因为此时的left已经left--过了,所以此时最长回文子串的起始位置是maxStart+1的位置.
6.用substring()方法去截取此时的最长回文子串.
s.substring(maxStart+1,maxStart+maxLen+1);
用maxStart+maxLen+1的原因是sunstring(x,y)方法只会截取到y-1的位置,y位置的元素不能被截取.

我感觉上面的文字叙述很清楚,就不麻烦的画图了啊~
代码如下:

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        int strLen = s.length();
        int left = 0;
        int right = 0;
        //当前情况的最长回文子串长度
        int len = 1;
        //子串开始的位置
        int maxStart = 0;
        //最长子串的长度
        int maxLen = 0;
        for(int i=0;i<strLen;i++){
            //中心元素左侧的位置
            left=i-1;
            //中心元素右侧的位置
            right=i+1;
            //判断left位置元素和i位置元素是否相等
            while(left>=0 && s.charAt(left)==s.charAt(i)){
                left--;
                len++;
            }
            //判断right位置元素和i位置元素是否相等
            while(right<strLen && s.charAt(right)==s.charAt(i)){
                right++;
                len++;
            }
            //判断left和right位置元素是否相等
            while(left>=0 && right<strLen &&
                  s.charAt(left)==s.charAt(right)){
                len+=2;
                left--;
                right++;
            }
            //将回文子串的最大值和初始位置保存起来.
            if(len>maxLen){
                maxLen=len;
                maxStart=left;
            }
            len=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
37
38
39
40
41
42
43
44
45
46
47