回文串问题总结_7-1 回文串问题

1.最长回文子串

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

示例 1：

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

输入: "cbbd"
输出: "bb"
1
2
3
4
5
6
7
8
9
10
11

1. 中心传播法，在每个元素中间插入‘#’来适应偶数回文串的情况，再遍历数组，每次遍历一个字符时，将该字符作为中心字符，向两边遍历，如果相等，就相加记录，最后找出最大的回文串。

class Solution {
public:
    string longestPalindrome(string s) {
        string str;
        str += '#';
        string maxstr;
        int maxsize = 0;
        for(auto c:s)
            str = str + c + '#';
        for(int i = 0; i < str.size(); i++){
            int l = i-1;
            int r = i+1;
            int count = 1;
            while(l >= 0 && r < str.size() && str[l] == str[r]){
                count++;
                l--;
                r++;
            }
            if(count > maxsize){
                maxsize = count;
                maxstr = str.substr(l+1, count*2-1);
            }
        }
        for(auto it = maxstr.begin(); it != maxstr.end(); ){
            if(*it == '#')
                it = maxstr.erase(it);
            else
                it++;
        }
        return maxstr;
    }
};
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

2. 自底向上的动态规划，步长为1和步长为2作为初始条件(步长为1是一个字符时，步长为2时相邻两个字符相等的情况)，然后从步长为3开始执行动态规划。

class Solution {
public:
    string longestPalindrome(string s) {
        int len=s.size();
        if(len==0||len==1)
            return s;
        int start=0;//回文串起始位置
        int max=1;//回文串最大长度
        vector<vector<int>>  dp(len,vector<int>(len));//定义二维动态数组
        for(int i=0;i<len;i++)//初始化状态
        {
            dp[i][i]=1;
            if(i<len-1&&s[i]==s[i+1])
            {
                dp[i][i+1]=1;
                max=2;
                start=i;
            }
        }
        for(int l=3;l<=len;l++)//l表示检索的子串长度，等于3表示先检索长度为3的子串
        {
            for(int i=0;i+l-1<len;i++)
            {
                int j=l+i-1;//终止字符位置
                if(s[i]==s[j]&&dp[i+1][j-1]==1)//状态转移
                {
                    dp[i][j]=1;
                    start=i;
                    max=l;
                }
            }
        }
        return s.substr(start,max);//获取最长回文子串
    }
};
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