5. 最长回文子串

Difficulty: 中等

给你一个字符串 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 仅由数字和英文字母（大写和/或小写）组成

Solution

Language: ****

https://uploadfiles.nowcoder.com/images/20210714/500979850_1626229769086/FC2271931B0332FF8EE94F7551775BB0

这里的解空间其实是一个倒三角，没必要遍历整个矩阵，只需要 从 最右下角的 顶角开始 遍历就可以了

所以下面的代码 是 $ l$ 从 $n-1$开始， $r$从 $l$ 开始往右边去遍历

 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

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n+1,vector<bool>(n+1));
        //dp[i][j] = dp[i+1][j-1] && s[i] == s[j]
        // for(int i=0;i<n;++i)
        //     dp[i][i] = true;
        int maxLen=1,i=0,j = 0;
        for(int l=n-1;l>=0;--l) {
            for(int r= l;r<n;++r) {
                if(l==r) dp[l][r] = true;
                else if (r==l+1)
                    dp[l][r] = s[l]==s[r];
                // if(l<r) {
                else 
                    dp[l][r] = dp[l+1][r-1] && (s[l] == s[r]);
                   
                // }
                if(dp[l][r] && r-l+1>maxLen) {
                    maxLen = r-l+1;
                    i = l,j = r;
                }
            }
        }
        return s.substr(i,maxLen);
        // return dp[0][n-1];
    }
};

求解最长回文字串的长度

将上面的代码 ，改为 return maxLen

分割回文字串

剑指 Offer II 086. 分割回文子字符串

Difficulty: 中等

给定一个字符串 s ，请将 s 分割成一些子串，使每个子串都是 回文串 ，返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

示例 1：

1
2

输入：s = "google"
输出：[["g","o","o","g","l","e"],["g","oo","g","l","e"],["goog","l","e"]]

示例 2：

1
2

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 3：

1
2

输入：s = "a"
输出：[["a"]

提示：

  • 1 <= s.length <= 16
  • s 仅由小写英文字母组成

注意：本题与主站 131 题相同：

Solution

Language: ****

 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

class Solution {
public:
    vector<vector<string>> partition(string s) {
        if(s.size()==0) return res;
        int n = s.size();
        dp = vector(n,vector<bool>(n));
        // dp[0][0] = 1;
        for(int l=n-1;l>=0;--l) {
            for(int r = l;r<n; ++r) {
                if(l==r) dp[l][r] = true;
                else if (r-l==1) {
                    dp[l][r] = (s[l] == s[r]);
                }
                else {
                    dp[l][r] = dp[l+1][r-1] && (s[l] == s[r]);
                }
            }
        }
        dfs(0,s,n);
        return res;


        

    }
    vector<vector<bool>> dp;
    vector<vector<string>> res;
    vector<string> path;
    void dfs(int cur ,string &s,int maxN) {
        if(cur == maxN) {
            res.push_back(path);
            return;
        }
        //如果是全排列的话，就从 0->N
        //如果是 序列选择的话，从 cur->N
        for(int i=cur;i<maxN;++i) {
            if(dp[cur][i]) {
               // [i,cur] 是回文来的
               path.push_back(s.substr(cur,i - cur  + 1));
               dfs(i+1,s,maxN);
               path.pop_back();
            }
        }

    }






};