LeetCode 5. Longest Palindromic Substring

发表于 更新于 分类于 阅读次数：

LeetCode 5. Longest Palindromic Substring 最长回文子串

给定一个字符串 s，找到s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

1
2
3
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

1
2
输入: "cbbd"
输出: "bb"

看到题目最容易想到的解决办法就是把这两个有序数组合并为一个有序数组，这样根据这一个有序数组就能很方便的找到中位数。

Java题解1：

按照上述思路可以得到下面的解法，合并为一个数组时间复杂度为\(O(m+n)\)。

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
/**
 * 回文字符串有两种情况，如果是abba即是偶数个，走loop1，如果是abcba走loop2
 * 用max记录最长长度，len1&len2记录当前长度，dev1&dev2记录距离中心点的长度
 * 
 * @param s
 * @return
 */
public String longestPalindrome(String s) {
    char[] chars = s.toCharArray();
    if (s.length() == 0) {
        return "";
    }
    int max = 1;
    int index = 0;
    for (int i = 0; i < chars.length; i++) {
        if (i > 0) {
            int dev1 = 0;
            int len1 = 0;
			// abba
            loop1: while (i - dev1 > 0 && i + dev1 < chars.length) { 
                if (chars[i + dev1] == chars[i - dev1 - 1]) {
                    len1 = len1 + 2;
                    if (len1 > max) {
                        max = len1;
                        index = i + dev1;
                    }
                    dev1++;
                } else {
                    break loop1;
                }
            }
            if (i > 1) {
                int dev2 = 0;
                int len2 = 1;
                // abcba
                loop2: while (i - dev2 - 1 > 0 && i + dev2 < chars.length) { 
                    if (chars[i + dev2] == chars[i - dev2 - 2]) {
                        len2 = len2 + 2;
                        if (len2 > max) {
                            max = len2;
                            index = i + dev2;
                        }
                        dev2++;
                    } else {
                        break loop2;
                    }
                }
            }
        }
    }
    return s.substring(index - max + 1, index + 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
/**
 * 把每次判断的代码提取出来
 * 
 * @param s
 * @return
 */
public String longestPalindrome2(String s) {
    int n = s.length();

    int[] range = new int[2];
    for (int i = 0; i < n; i++) {
        i = helper(s, range, i);
    }

    return s.substring(range[0], range[1]);
}

public int helper(String s, int[] range, int i) {
    int lo = i;
    int hi = i;
    while (hi < s.length() - 1 && s.charAt(hi) == s.charAt(hi + 1)) {
        hi++;
    }

    int ret = hi;
    while (lo > 0 && hi < s.length() - 1 && s.charAt(lo - 1) == s.charAt(hi + 1)) {
        lo--;
        hi++;
    }

    if (hi - lo + 1 > range[1] - range[0]) {
        range[0] = lo;
        range[1] = hi + 1;
    }

    return ret;
}