最长回文子串

发表于 | 分类于 | 阅读次数：
本文字数： 3.6k | 阅读时长 ≈ 9 分钟

问题提出

#5 Longest Palindromic Substring

如何快速找出一个字符串的最长回文子串？

一般思路

从中间向外找，一共有2n-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
// 代码引自leetcode官方解答
// https://leetcode-cn.com/problems/longest-palindromic-substring/solution
public String longestPalindrome(String s) {
    if (s == null || s.length() < 1) return "";
    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        int len1 = expandAroundCenter(s, i, i);
        int len2 = expandAroundCenter(s, i, i + 1);
        int len = Math.max(len1, len2);
        if (len > end - start) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    return s.substring(start, end + 1);
}

private int expandAroundCenter(String s, int left, int right) {
    int L = left, R = right;
    while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
        L--;
        R++;
    }
    return R - L - 1;
}

该算法的时间复杂度为O(n2)， 已经可以通过测试了，但还有更佳的算法。

优化算法

规律探究

1
2
     012345678
s = 'abcdedcbf';

以字符串s为例，如果使用上述中心扩展的方法，依次以各个字母为中心扩展，考虑第5位和第6位

  • 当中心移至第5位d时，我们已经知道了以第3位d为中心的最长回文子串长度为1，以第4位e为中心的最长子串长度为7。需要注意的是，第5位和第3位关于第4位对称，由此可以判断：以第5位为中心的最长子串的长度也为1

    1
    2
    3
    4为中心的最长子串有7位 => s[1:3]=s[5:7]
    3为中心的最长子串有1位 => s[2]!=s[4]
    => s[6]!=s[4] => 5位中心的最长子串只有1位

  • 同理，当中心移至第6位c时，我们已知以第2位d为中心的最长子串长度为3。第6位和第2位关于第4位对称，且第4位最长子串包含了第2位的最长子串，由此可以判断：以第6位为中心的最长子串长度不小于3

总结起来，我们要充分利用之前的计算结果，避免重复无意义的计算。

右边界十分重要！

在上面的规律探究中，第7位非常重要，因为在计算完以第4位为中心的最长子串后，能到达的最右边的位置是第7位，因此在上例中，我们计算第5和第6位时，都可以直接使用之前的结论。在我们计算第7位时，由于到达了之前计算的最右边界，就没有可以利用的数据了。

因此，在我们设计算法时，要记录下当前计算到的右边界的位置，同时也要记录下到达该右边界的中心点。以后每次计算一个新的中心点时，先要查看该点是否在这个右边界的范围内，如果在，说明一定有可以利用的结论，如果不在，就按照之前的办法中心扩展，如果到达了更右边的位置，就更新右边界。

一个小trick

在中心扩展时，不得不考虑两种情况，一种是中心有字母（如aba），另一种是中心没字母（如abba）。一种处理的办法是在每两个字母间（包括头尾）加入一个特殊字符，例如abba->#a#b#b#a#a#，这将就将问题转化成了中心有字母的情况

算法总结

  1. 字符串预处理
  2. 遍历字符串，计算以当前字符为中心的最长子串的长度
  3. 每次迭代时，判断该字符是否在最右边界范围内。如果在范围内，根据对称性得到已知回文串的长度，如果到达了边界，继续扩展。如果不在范围内，开始中心扩展。每次中心扩展时，要更新右边界。
  4. 得到最长回文串，去除特殊字符即可

复杂度分析

以最右边界为基准，每次遍历的时候，要么在最右边界范围内，直接得到结果；要么超出了最右边界，则最右边界得到了更新。因此时间复杂度与最右边界数成正比，为O(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
string longestPalindrome(string s) {
    encode(s);
    int str_length = s.length();

    int right_most = 0;
    int right_most_center = 0;
    int longest_center = 0;
    int longest_halfLen = 0;
    int *str_table = new int[str_length];
    for (int cur = 0; cur < str_length; cur++) {
        int halfLen = 0;
        if (cur < right_most) {
            int mirror = 2 * right_most_center - cur;
            if (mirror >= 0) halfLen = str_table[halfLen];
        }
        for (; cur - halfLen - 1 >= 0 && cur + halfLen + 1 < str_length; halfLen++) {
            if (s[cur - halfLen - 1] != s[cur + halfLen + 1]) break;
        }
        str_table[cur] = halfLen;
        if (halfLen + cur > right_most) {
            right_most = halfLen + cur;
            right_most_center = cur;
        }
        if (halfLen > longest_halfLen) {
            longest_center = cur;
            longest_halfLen = halfLen;
        }
    }

    string ret = s.substr(longest_center - longest_halfLen, 2 * longest_halfLen + 1);
    decode(ret);
    delete(str_table);
    return ret;
}

void encode(string &s) {
    for (int i = s.length(); i >= 0; i--)
        s.insert(i, "#");
}

void decode(string &s) {
    string ret;
    for (size_t i = 0; i < s.length(); i++) {
        if (s[i] != '#') ret += s[i];
    }
    s = ret;
}