LeetCode 刷题笔记——day 4

5. 最长回文子串

难度：中等

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

示例 1：

1
2
3
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

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

示例 3：

1
2
输入：s = "a"
输出："a"

示例 4：

1
2
输入：s = "ac"
输出："a"

提示：

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母（大写和/或小写）组成

我的答案

小白经典做题法，暴力且耐心。

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
class Solution {
public:
    string longestPalindrome(string s) {
        int max = 0, len;
        char* ch = &s[0];

        for(int i = 1; i < s.size(); i++) {
            if(s[i] == s[i - 1]) {
                len = 2;
                if(max < len) {
                    ch = &s[i - 1];
                }
                for(int j = i + 1; ; j++) {
                    int n = i * 2 - j - 1;
                    if(n >= 0 && s[n] == s[j] && j < s.size()) {
                        len += 2;
                    } else {
                        if(max < len) {
                            ch = &s[n + 1];
                        }
                        max = max > len ? max : len;
                        len = 0;
                        break;
                    }
                }
            }
            if(i > 1 && s[i] == s[i - 2]) {
                len = 3;
                if(max < len) {
                    ch = &s[i - 2];
                }
                for(int j = i + 1; ; j++) {
                    int n = i * 2 - j - 2;
                    if(n >= 0 && s[n] == s[j] && j < s.size()) {
                        len += 2;
                    } else {
                        if(max < len) {
                            ch = &s[n + 1];
                        }
                        max = max > len ? max : len;
                        len = 0;
                        break;
                    }
                }
            }
        }
        if(s.size() > 0 && max == 0) {
            max = 1;
        }

        string str(ch, max);
        return str;
    }
};

  • 执行用时: 16 ms

  • 内存消耗: 7.1 MB

官方答案

在官方题解中，提供了三种不同的算法：

动态规划

思路与算法

对于一个子串而言，如果它是回文串，并且长度大于 22，那么将它首尾的两个字母去除之后，它仍然是个回文串。例如对于字符串“ababa”\textrm{“ababa”}，如果我们已经知道“bab"\textrm{“bab"} 是回文串，那么“ababa”\textrm{“ababa”} 一定是回文串，这是因为它的首尾两个字母都是“a”\textrm{“a”}。

根据这样的思路，我们就可以用动态规划的方法解决本题。我们用P(i,j)P(i,j) 表示字符串ss 的第ii 到jj 个字母组成的串（下文表示成s[i:j]s[i:j]）是否为回文串：

P(i,j)={true,如果子串 Si…Sj 是回文串false,其它情况P(i,j) = \begin{cases} \text{true,} &\quad\text{如果子串~} S_i \dots S_j \text{~是回文串}\\ \text{false,} &\quad\text{其它情况} \end{cases}

这里的「其它情况」包含两种可能性：

s[i,j]s[i, j] 本身不是一个回文串；

i>ji > j，此时s[i,j]s[i, j] 本身不合法。

那么我们就可以写出动态规划的状态转移方程：

P(i,j)=P(i+1,j−1)∧(Si==Sj)P(i, j) = P(i+1, j-1) \wedge (S_i == S_j)

也就是说，只有s[i+1:j−1]s[i+1:j-1] 是回文串，并且ss 的第ii 和jj 个字母相同时，s[i:j]s[i:j] 才会是回文串。

上文的所有讨论是建立在子串长度大于22 的前提之上的，我们还需要考虑动态规划中的边界条件，即子串的长度为11 或22。对于长度为11 的子串，它显然是个回文串；对于长度为22 的子串，只要它的两个字母相同，它就是一个回文串。因此我们就可以写出动态规划的边界条件：

{P(i,i)=trueP(i,i+1)=(Si==Si+1)\begin{cases} P(i, i) = \text{true} \\ P(i, i+1) = ( S_i == S_{i+1} ) \end{cases}

根据这个思路，我们就可以完成动态规划了，最终的答案即为所有P(i,j)=trueP(i, j) = \text{true} 中j−i+1j-i+1（即子串长度）的最大值。注意：在状态转移方程中，我们是从长度较短的字符串向长度较长的字符串进行转移的，因此一定要注意动态规划的循环顺序。

作者：LeetCode-Solution

这里用 c++ 实现一遍：

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
class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();

        if(n < 2) {
            return s;
        }

        int max = 1;
        int begin = 0;
        vector<vector<bool>> b_e(n, vector<bool>(n));
        for(int i = 0; i < n; i++) {
            b_e[i][i] = true;
        }

        for(int len = 2; len <= n; len++) {
            for(int i = 0; i < n; i++) {
                int j = i + len - 1;
                if(j >= n) {
                    break;
                }

                if(s[i] != s[j]) {
                    b_e[i][j] = false;
                } else {
                    if(j - i < 3) {
                        b_e[i][j] = true;
                    } else {
                        b_e[i][j] = b_e[i + 1][j - 1];
                    }
                }

                if(b_e[i][j] && j - i + 1 > max) {
                    max = j - i + 1;
                    begin = i;
                }
            }
        }

        return s.substr(begin, max);
    }
};

  • 执行用时: 568 ms

  • 内存消耗: 29.5 MB

动态规划的方法在效率上确实没眼看，甚至我的代码都要优秀很多，但不得不说，用二维数组来做题是我没有想过的，原理还是很巧妙的。就做题思想来说，作为小白，要学习的真的太多了，希望对算法的学习能成功从刷题开始一直深入。如果有小白也刷到这里，应该也会感到很无力吧，愿大家都能坚持到底。哦，才第五题啊，那没事了~

继续练习练习 Java 实现：

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
class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();

        if(n < 2) {
            return s;
        }

        int max = 1;
        int begin = 0;
        boolean[][] b_e = new boolean[n][n];
        char[] s0 = s.toCharArray();
        for(int i = 0; i < n; i++) {
            b_e[i][i] = true;
        }

        for(int len = 2; len <= n; len++) {
            for(int i = 0; i < n; i++) {
                int j = i + len - 1;
                if(j >= n) {
                    break;
                }

                if(s0[i] != s0[j]) {
                    b_e[i][j] = false;
                } else {
                    if(j - i < 3) {
                        b_e[i][j] = true;
                    } else {
                        b_e[i][j] = b_e[i + 1][j - 1];
                    }
                }

                if(b_e[i][j] && j - i + 1 > max) {
                    max = j - i + 1;
                    begin = i;
                }
            }
        }

        return s.substring(begin, begin + max);
    }
}

  • 执行用时: 165 ms

  • 内存消耗: 42.9 MB

官方题解的第二种解法：

中心扩展算法

思路与算法

我们仔细观察一下方法一中的状态转移方程：

{P(i,i)=trueP(i,i+1)=(Si==Si+1)P(i,j)=P(i+1,j−1)∧(Si==Sj)\begin{cases} P(i, i) &=\quad \text{true} \\ P(i, i+1) &=\quad ( S_i == S_{i+1} ) \\ P(i, j) &=\quad P(i+1, j-1) \wedge (S_i == S_j) \end{cases}

找出其中的状态转移链：

P(i,j)←P(i+1,j−1)←P(i+2,j−2)←⋯←某一边界情况P(i, j) \leftarrow P(i+1, j-1) \leftarrow P(i+2, j-2) \leftarrow \cdots \leftarrow \text{某一边界情况}

可以发现，所有的状态在转移的时候的可能性都是唯一的。也就是说，我们可以从每一种边界情况开始「扩展」，也可以得出所有的状态对应的答案。

边界情况即为子串长度为11 或22 的情况。我们枚举每一种边界情况，并从对应的子串开始不断地向两边扩展。如果两边的字母相同，我们就可以继续扩展，例如从P(i+1,j−1)P(i+1,j−1) 扩展到P(i,j)P(i,j)；如果两边的字母不同，我们就可以停止扩展，因为在这之后的子串都不能是回文串了。

聪明的读者此时应该可以发现，「边界情况」对应的子串实际上就是我们「扩展」出的回文串的「回文中心」。方法二的本质即为：我们枚举所有的「回文中心」并尝试「扩展」，直到无法扩展为止，此时的回文串长度即为此「回文中心」下的最长回文串长度。我们对所有的长度求出最大值，即可得到最终的答案。

作者：LeetCode-Solution

用 c++ 实现了一下这个方法：

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
class Solution {
public:
    pair<int, int> hanshu(const string& s, int start, int end) {
        while(start >= 0 && end <= s.size() && s[end] == s[start]){
            --start;
            ++end;
        }

        return {++start, --end};
    }
    string longestPalindrome(string s) {
        int start = 0, end = 0;
        for(int i = 0; i < s.size(); i++) {
            auto [start1, end1] = hanshu(s, i, i);
            auto [start2, end2] = hanshu(s, i, i + 1);
            if(end1 - start1 > end - start) {
                start = start1;
                end = end1;
            }
            if(end2 - start2 > end - start) {
                start = start2;
                end = end2;
            }
        }

        return s.substr(start, end - start + 1);
    }
};

  • 执行用时: 20 ms

  • 内存消耗: 6.8 MB

看完题解，发现这个方法原理就是我的初始代码，那么问题来了，相同原理怎么别人设计的程序就这么精炼巧妙……

依然练习练习使用 Java 来实现：

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
class Solution {
    public String longestPalindrome(String s) {
        if(s.length() < 2) {
            return s;
        }
        int start = 0, end = 0;
        for(int i = 0; i < s.length(); i++) {
            int len1 = hanshu(s, i, i);
            int len2 = hanshu(s, i, i + 1);
            int len = Math.max(len1, len2);
            if(len > end - start + 1) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    public int hanshu(String s , int start, int end) {
        while(start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)) {
            --start;
            ++end;
        }
        return end - start - 1;
    }
}

  • 执行用时: 25 ms

  • 内存消耗: 38.6 MB

每次都对着修改到一模一样才能通过编译……

官方的第三种解法是：

Manacher 算法（据说非常复杂）

为了表述方便，我们定义一个新概念臂长，表示中心扩展算法向外扩展的长度。如果一个位置的最大回文字符串长度为 2 * length + 1 ，其臂长为 length。

下面的讨论只涉及长度为奇数的回文字符串。长度为偶数的回文字符串我们将会在最后与长度为奇数的情况统一起来。

思路与算法

在中心扩展算法的过程中，我们能够得出每个位置的臂长。那么当我们要得出以下一个位置 i 的臂长时，能不能利用之前得到的信息呢？

答案是肯定的。具体来说，如果位置 j 的臂长为 length，并且有 j + length > i，如下图所示：

当在位置 i 开始进行中心拓展时，我们可以先找到 i 关于 j 的对称点 2 * j - i。那么如果点 2 * j - i 的臂长等于 n，我们就可以知道，点 i 的臂长至少为 min(j + length - i, n)。那么我们就可以直接跳过 i 到 i + min(j + length - i, n) 这部分，从 i + min(j + length - i, n) + 1 开始拓展。

我们只需要在中心扩展法的过程中记录右臂在最右边的回文字符串，将其中心作为 j，在计算过程中就能最大限度地避免重复计算。

那么现在还有一个问题：如何处理长度为偶数的回文字符串呢？

我们可以通过一个特别的操作将奇偶数的情况统一起来：我们向字符串的头尾以及每两个字符中间添加一个特殊字符 #，比如字符串 aaba 处理后会变成 #a#a#b#a#。那么原先长度为偶数的回文字符串 aa 会变成长度为奇数的回文字符串 #a#a#，而长度为奇数的回文字符串 aba 会变成长度仍然为奇数的回文字符串 #a#b#a#，我们就不需要再考虑长度为偶数的回文字符串了。

注意这里的特殊字符不需要是没有出现过的字母，我们可以使用任何一个字符来作为这个特殊字符。这是因为，当我们只考虑长度为奇数的回文字符串时，每次我们比较的两个字符奇偶性一定是相同的，所以原来字符串中的字符不会与插入的特殊字符互相比较，不会因此产生问题。

作者：LeetCode-Solution

主题思路与「中心扩展算法」一样，但增加了避免重复计算的语句，经典以头发换效率。这里贴出官方 C++ 源代码，日后复习再复现一遍：

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
class Solution {
public:
    int expand(const string& s, int left, int right) {
        while (left >= 0 && right < s.size() && s[left] == s[right]) {
            --left;
            ++right;
        }
        return (right - left - 2) / 2;
    }

    string longestPalindrome(string s) {
        int start = 0, end = -1;
        string t = "#";
        for (char c: s) {
            t += c;
            t += '#';
        }
        t += '#';
        s = t;

        vector<int> arm_len;
        int right = -1, j = -1;
        for (int i = 0; i < s.size(); ++i) {
            int cur_arm_len;
            if (right >= i) {
                int i_sym = j * 2 - i;
                int min_arm_len = min(arm_len[i_sym], right - i);
                cur_arm_len = expand(s, i - min_arm_len, i + min_arm_len);
            } else {
                cur_arm_len = expand(s, i, i);
            }
            arm_len.push_back(cur_arm_len);
            if (i + cur_arm_len > right) {
                j = i;
                right = i + cur_arm_len;
            }
            if (cur_arm_len * 2 + 1 > end - start) {
                start = i - cur_arm_len;
                end = i + cur_arm_len;
            }
        }

        string ans;
        for (int i = start; i <= end; ++i) {
            if (s[i] != '#') {
                ans += s[i];
            }
        }
        return ans;
    }
};

作者：LeetCode-Solution
  • 执行用时: 8 ms
  • 内存消耗: 10.9 MB

这里用 Java 复现一遍：

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
class Solution {
    public String longestPalindrome(String s) {
        StringBuffer sb = new StringBuffer("#");
        for(int i = 0; i < s.length(); i++) {
            sb.append(s.charAt(i));
            sb.append('#');
        }
        s = sb.toString();

        List<Integer> arm_len = new ArrayList<Integer>();
        int start = 0, end = -1, right = -1, j = -1;
        for(int i = 0; i < s.length(); i++) {
            int len;
            if(right >= i) {
                int i0 = j * 2 - i;
                int min = Math.min(arm_len.get(i0), right - i);
                len = hanshu(s, i - min, i + min);
            } else {
                len = hanshu(s, i, i);
            }
            arm_len.add(len);
            if(i + len > right) {
                j = i;
                right = i + len;
            }
            if(len * 2 + 1 > end - start) {
                start = i - len;
                end = i + len;
            }
        }

        StringBuffer sb0 = new StringBuffer();
        for(int i = start; i <= end; i++) {
            if(s.charAt(i) != '#') {
                sb0.append(s.charAt(i));
            }
        }

        return sb0.toString();
    }

    public int hanshu(String s , int start, int end) {
        while(start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)) {
            --start;
            ++end;
        }
        return (end - start - 2) / 2;
    }
}

  • 执行用时: 19 ms

  • 内存消耗: 38.9 MB

总结

虽然篇幅不小，但今天依旧只做了一道题……