力扣—最长回文子串

题目来自力扣（leetcode）

题目

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

示例：

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

思路

回文，指的是正着读和反着读相同的字符串，比如“abcba”，“12321”

中心扩散法

所谓“中心扩散法”，指的是从中心向左和向右开始找，直到left≠right，这个过程中能找到的最长的回文子串即为该问题的解

当然，一开始肯定不会知道从哪开始找是最长的回文子串，所以需要使用循环去比较。

public String longestPalindrome(String s) {

    //三种特殊的情况，null，空字符串，只有一个字符，那么就无需计算，直接返回结果即可
    if (s == null || s.length() == 0) {
        return "";
    }

    if(s.length() == 1){
        return s;
    }

    int maxLen = 0, tempLen = 0;  //maxLen用来记录字符串里最大回文的长度。tempLen用作每次循环临时使用的回文长度记录
    int minIndex = 0, tempMinIndex = 0, maxIndex = 0, tempMaxIndex = 0;  //记录回文的起始和结束索引，也分为总记录和每次循环的临时记录
    int len = 0;   //用于计算中间值到左右边界的记录  比如aba，对于b来说，到左右边界就是1

    for (int strIndex = 0; strIndex < s.length(); strIndex++) {
        if(strIndex == s.length()-1){    //循环结束的标志，因为没有右侧邻居，所以无需计算
            break;
        }

        if (s.charAt(strIndex) == s.charAt(strIndex + 1)){
            //abba这种相邻的两个值可以组成回文的情况
            tempLen = 2;
            tempMinIndex = strIndex;
            tempMaxIndex = strIndex + 1;
            len = Math.min(strIndex, s.length() - 2 - strIndex);
            for (int index1 = 1; index1 <= len; index1++) {
                if(s.charAt(strIndex - index1) == s.charAt(strIndex + 1 + index1)){
                    tempLen += 2;
                    tempMinIndex = strIndex - index1;
                    tempMaxIndex = strIndex + 1 + index1;
                }
                else{
                    break;
                }
            }

            if(tempLen > maxLen){   //对于strIndex这个中间值来说，需要将本次计算的回文长度与最大回文长度相比较
                maxLen = tempLen;
                maxIndex = tempMaxIndex;
                minIndex = tempMinIndex;
            }
        }

        if( strIndex >= 1 && s.charAt(strIndex - 1) == s.charAt(strIndex + 1)){
            //aba这种不是相邻的两个值可以组成回文的情况
            tempLen = 3;
            tempMinIndex = strIndex - 1;
            tempMaxIndex = strIndex + 1;
            len = Math.min(strIndex, s.length() - 1 - strIndex);
            for (int index2 = 2; index2 <= len; index2++) {
                if(s.charAt(strIndex - index2) == s.charAt(strIndex + index2)){
                    tempLen += 2;
                    tempMinIndex = strIndex - index2;
                    tempMaxIndex = strIndex + index2;
                }
                else{
                    break;
                }
            }
            if(tempLen > maxLen){   //对于strIndex这个中间值来说，需要将本次计算的回文长度与最大回文长度相比较
                maxLen = tempLen;
                maxIndex = tempMaxIndex;
                minIndex = tempMinIndex;
            }
        }
    }

    return s.substring(minIndex, maxIndex + 1);   //截取根据索引截取字符串，因为截取的区间是左闭右开，所以右侧需要+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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

关于截取字符串.substring()，一些同学喜欢在半路截取，也就是获取一个比较长的字符串的时候就去截取出来，等到有更长的再替换掉，这里不建议这么做，虽然程序可以运行，但是截取字符串这个操作非常耗时，并且占用空间也大，所以还是建议只保存索引，到最后再截取。

测试

这里写了一个测试的方法，用了几种常见的类型，当然你可以自己加其它类型，自行判断输出的结果是否与预期相同（用到了junit工具）

@Test
public void test(){
    String[] testStrs = new String[]{"", "a", "abc", "aba", "abcc", "abba", "aaa", "aaaa"};
    for (int testIndex = 0; testIndex < testStrs.length; testIndex++) {
        System.out.println("最长回文：" + longestPalindrome(testStrs[testIndex]));
    }
}
1
2
3
4
5
6
7