1 题目

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

示例1

1
2
3

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

示例2

1
2

输入: "cbbd"
输出: "bb"

2 解题

2.1 动态规划

思路

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

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

$$ P(i,j) = \begin{cases} & true \ \ 如果字串S_i…S_j是回文串\\
& false \ 其他情况 \end{cases} $$ 这里的「其它情况」包含两种可能性：

  • s[i,j] 本身不是一个回文串;
  • i>j，此时 s[i,j] 本身不合法。

那么我们就可以写出动态规划的状态转移方程： $$ P(i,j) = P(i+1,j-1) \land (S_i == S_j) $$ 也就是说，只有 s[i+1:j−1] 是回文串，并且 s 的第 i和 j 个字母相同时，s[i:j] 才会是回文串。

上文的所有讨论是建立在子串长度大于 2 的前提之上的，我们还需要考虑动态规划中的边界条件，即子串的长度为 1 或 2。对于长度为 1 的子串，它显然是个回文串；对于长度为 2 的子串，只要它的两个字母相同，它就是一个回文串。因此我们就可以写出动态规划的边界条件： $$ \begin{cases} &P(i,j) = true\\
&P(i,i+1)=(S_i==S_{i+1}) \end{cases} $$ 根据这个思路，我们就可以完成动态规划了，最终的答案即为所有$ P(i, j) = {true}$ 中 j−i+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

string longestPalindrome(string s) 
{
    int n = s.size();
    //字符串为空或者长度为1
    if (n < 2) 
    {
        return s;
    }

    int maxLen = 1;
    int begin = 0;
    // dp[i][j] 表示 s[i..j] 是否是回文串
    // 二维数组表征
    vector<vector<int>> dp(n, vector<int>(n));
    // 初始化：所有长度为 1 的子串都是回文串
    for (int i = 0; i < n; i++) 
    {
        dp[i][i] = true;
    }
    // 递推开始
    // 先枚举子串长度，L表示子串长度
    for (int L = 2; L <= n; L++) 
    {
        // 枚举左边界，左边界的上限设置可以宽松一些
            for (int i = 0; i < n; i++) 
            {
                // 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                int j = L + i - 1;
                // 如果右边界越界，就可以退出当前循环
                if (j >= n) 
                {
                    break;
                }

                if (s[i] != s[j]) 
                {
                    dp[i][j] = false;
                } 
                else 
                {
                    //长度小于等于3，边界条件
                    if (j - i < 3) 
                    {
                        dp[i][j] = true;
                    } 
                    //状态转移方程
                    else 
                    {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }

                // 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，
                //判断此时的长度是否最长，若是记录回文长度和起始位置
                if (dp[i][j] && j - i + 1 > maxLen) 
                {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substr(begin, maxLen);
    //该函数的意思是获取从begin开始长度为maxlen长度的字符串
    }
};

复杂度分析：

  • 时间复杂度：$O(n^2)$,其中 n 是字符串的长度。动态规划的状态总数 $O(n^2)$，对于每个状态，我们需要转移的时间为 $O(1)$。

  • 空间复杂度：$O(n^2)$，即存储动态规划状态需要的空间。

2.2 中心扩展算法

思路

2.1中的状态转移方程： $$ \begin{cases} &P(i,j) = true\\
&P(i,i+1)=(S_i==S_{i+1}) \\
&P(i,j) = P(i+1,j-1) \land (S_i == S_j) \end{cases} $$ 找出其中的状态转移链： $$ P(i,j) \leftarrow P(i+1,j-1) \leftarrow P(i+2,j-2) \leftarrow…\leftarrow 某一边界条件 $$ 可以发现，**所有的状态在转移的时候的可能性都是唯一的**。也就是说，我们可以从每一种边界情况开始「扩展」，也可以得出所有的状态对应的答案。

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

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

代码实现：

 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

std::string longestPalindrome(std::string s) 
{
    int start = 0, end = 0;
    //以第i个位置为中心或者i，i+1（偶数回文，且i与i+1字符一致）两个为中心
    for (int i = 0; i < s.size(); i++)
    {
        int len1 = expandAroundCenter(s, i, i);
        int len2 = expandAroundCenter(s, i, i + 1);
        int len = (len1 > len2) ? len1 : len2;
        if (len > end - start) 
        {
            //从i位置向分别向左或是向右扩展len/2个长度
            //若len为奇数，分别向左向右扩展（len-1）/2
            //若len为偶数，向左扩展len/2 - 1，向右扩展len/2
            //其中len为奇时，（len-1）/2 与 len/2值一样
            //len为偶时，len/2 - 1 与（len-1）/2值一样
            //故向左（len-1）/2，向右len/2
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    return s.substr(start, end + 1 - start);
}

int expandAroundCenter(std::string s, int left, int right)
{
    int L = left, R = right;
    while (L>=0 && R < s.size() && s[L] == s[R])
    {
        L--;
        R++;
    }
    //若是（i,i）传进来，多计算了一次L--与R++
    //此时相当于左边下标等于L+1，右边下标等于R-1，
    //长度为R-1-（L+1）+1=R-L-1
    //同理若（i，i+1）起始是回文也是一样的，多计算了一次
    //若不是的话，返回值为0
    return R - L - 1;
}

复杂度分析：

  • 时间复杂度：$O(n^2)$。

    其中 n 是字符串的长度。长度为 1 和 2 的回文中心分别有 n 和 n−1 个，每个回文中心最多会向外扩展 $O(n)$次。

  • 空间复杂度:$O(1)$。