Justice's Site

最长回文子串

 滴水穿石  416  2 分钟

最长回文子串

CategoryDifficultyLikesDislikes
algorithmsMedium (28.58%)1805-

Tags

string | dynamic-programming

Companies

amazon | bloomberg | microsoft

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

示例 1：

1
2
3

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

示例 2：

1
2

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

Discussion | Solution

解法

动态规划

1、定义 “状态”，这里 “状态”数组是二维数组。

dp[l][r] ：表示子串  s[l, r]（包括区间左右端点）是否构成回文串，是一个二维布尔型数组。即如果子串  s[l, r]  是回文串，那么  dp[l][r] = true。

2、找到 “状态转移方程”。

首先，我们很清楚一个事实：

1、当子串只包含  1  个字符，它一定是回文子串；

2、当子串包含 2 个以上字符的时候：如果  s[l, r]  是一个回文串，例如  “abccba”，那么这个回文串两边各往里面收缩一个字符（如果可以的话）的子串  s[l + 1, r - 1]  也一定是回文串，即：如果  dp[l][r] == true  成立，一定有  dp[l + 1][r - 1] = true  成立。

根据这一点，我们可以知道，给出一个子串  s[l, r] ，如果  s[l] != s[r]，那么这个子串就一定不是回文串。如果  s[l] == s[r]  成立，就接着判断  s[l + 1] 与 s[r - 1]，这很像中心扩散法的逆方法。

事实上，当  s[l] == s[r]  成立的时候，dp[l][r]  的值由  dp[l + 1][r - l]  决定，这一点也不难思考：当左右边界字符串相等的时候，整个字符串是否是回文就完全由“原字符串去掉左右边界”的子串是否回文决定。但是这里还需要再多考虑一点点：“原字符串去掉左右边界”的子串的边界情况。

1、当原字符串的元素个数为  33  个的时候，如果左右边界相等，那么去掉它们以后，只剩下  11  个字符，它一定是回文串，故原字符串也一定是回文串；

2、当原字符串的元素个数为  22  个的时候，如果左右边界相等，那么去掉它们以后，只剩下  00  个字符，显然原字符串也一定是回文串。

把上面两点归纳一下，只要  s[l + 1, r - 1]  至少包含两个元素，就有必要继续做判断，否则直接根据左右边界是否相等就能得到原字符串的回文性。而“s[l + 1, r - 1]  至少包含两个元素”等价于  l + 1 < r - 1，整理得  l - r < -2，或者  r - l > 2。

综上，如果一个字符串的左右边界相等，以下二者之一成立即可： 1、去掉左右边界以后的字符串不构成区间，即“ s[l + 1, r - 1]  至少包含两个元素”的反面，即  l - r >= -2，或者  r - l <= 2； 2、去掉左右边界以后的字符串是回文串，具体说，它的回文性决定了原字符串的回文性。

于是整理成“状态转移方程”：

dp[l, r] = (s[l] == s[r] and (l - r >= -2 or dp[l + 1, r - 1]))

或者

dp[l, r] = (s[l] == s[r] and (r - l <= 2 or dp[l + 1, r - 1]))

编码实现细节：

因为要构成子串  l  一定小于等于  r ，我们只关心 “状态”数组“上三角”的那部分取值。理解上面的“状态转移方程”中的  (r - l <= 2 or dp[l + 1, r - 1])  这部分是关键，因为  or  是短路运算，因此，如果收缩以后不构成区间，那么就没有必要看继续  dp[l + 1, r - 1]  的取值。

读者可以思考一下：为什么在动态规划的算法中，不用考虑回文串长度的奇偶性呢。想一想，答案就在状态转移方程里面。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def longestPalindrome(self, s: str) -> str:
        size = len(s)
        if size < 2:
            return s
        dp = [ [ False for _ in range(size) ] for _ in range(size) ]
        longest = 1
        res = s[0]
        for r in range(1, size):
            for l in range(r):
                if s[l] == s[r] and ( r -l <=2 or dp[l+1][r-1] ):
                    dp[l][r] = True
                    cur_len = r - l + 1
                    if cur_len > longest:
                        longest = cur_len
                        res = s[l:r+1]

        return res

 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

impl Solution {
    /// ## 解题思路
    /// - 动态规划
    /// 1. 设dp[i][j]: s[i:j+1]是否为回文子串
    /// 2. 状态转移方程：dp[i][j] = (s[i] == s[j] && dp[i+1][j-1])
    /// 3. 初始条件：dp[i][i]=true
    pub fn longest_palindrome(s: String) -> String {
        let n = s.len();
        let mut dp = vec![vec![false; n]; n];
        for i in 0..n {
            dp[i][i] = true;
        }

        let mut longest = 1;
        let mut res: &str = &s[0..1];
        for r in 1..n {
            for l in 0..r {
                if s.chars().nth(l) == s.chars().nth(r) && (r-l<=2 || dp[l+1][r-1] ) {
                    dp[l][r] = true;
                    if r-l+1 > longest {
                        longest = r-l+1;
                        res = &s[l..r+1];
                    }
                }
            }
        }

        String::from(res)
    }
}

相关文章：