Leetcode 5. Longest Palindromic Substring

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

示例：

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

动态规划解法：秒懂算法的bilibili视频

代码位于文章末尾。

这里我举个例子：abcdedcaa

应该返回cdedc

下面的表格中，表头0-8对应着下标，表内的数值对应着Pa的值。横向表头对应i的值，纵向表头对应j的值。

	0	1	2	3	4	5	6	7	8
0	1	0	0	0	0	0	0	0	0
1	0	1	0	0	0	0	0	0	0
2	0	0	1	0	0	0	0	0	0
3	0	0	0	1	0	0	0	0	0
4	0	0	0	0	1	0	0	0	0
5	0	0	0	0	0	1	0	0	0
6	0	0	0	0	0	0	1	0	0
7	0	0	0	0	0	0	0	1	0
8	0	0	0	0	0	0	0	0	1

从i=0,j=0不断遍历，可以找到第一个回文字串是j=5,i=3处的ded

	0	1	2	3	4	5	6	7	8
0	1	0	0	0	0	0	0	0	0
1	0	1	0	0	0	0	0	0	0
2	0	0	1	0	0	0	0	0	0
3	0	0	0	1	0	0	0	0	0
4	0	0	0	0	1	0	0	0	0
5	0	0	0	1	0	1	0	0	0
6	0	0	0	0	0	0	1	0	0
7	0	0	0	0	0	0	0	1	0
8	0	0	0	0	0	0	0	0	1

往下寻找，可以发现j=6,i=2这个点同样也能找到回文字串cdedc,是在ded的基础上寻找到的。

	0	1	2	3	4	5	6	7	8
0	1	0	0	0	0	0	0	0	0
1	0	1	0	0	0	0	0	0	0
2	0	0	1	0	0	0	0	0	0
3	0	0	0	1	0	0	0	0	0
4	0	0	0	0	1	0	0	0	0
5	0	0	0	1	0	1	0	0	0
6	0	0	1	0	0	0	1	0	0
7	0	0	0	0	0	0	0	1	0
8	0	0	0	0	0	0	0	0	1

可以看出，这种方法是在单独的回文字串的基础上不断往两边扩展。首先的最小字串为一个字母，然后遍历i和j，i<j。发现i+1,j-1处为一个回文字串后拓展。

class Solution {
public:
    string longestPalindrome(string s) {
        if(s.size()==1) return s;
        int maxlength=1,startalpha=0;
        bool Pa[s.size()][s.size()];
        for(int i=0;i<s.size();i++) for(int j=0;j<s.size();j++) if(i==j) Pa[i][j]=true;else Pa[i][j]=false;
        for(int j=0;j<s.size();j++){
            for(int i=0;i<j;i++){
                if(s[i]==s[j]&&(j-i==1||Pa[i+1][j-1])) Pa[i][j]=true;
                if(Pa[i][j]&&j-i+1>maxlength){
                    startalpha=i;
                    maxlength=j-i+1;
                }
            }
        }
        return s.substr(startalpha,maxlength);
    }
};

LeetCode5 最长回文子串

Leetcode 5. Longest Palindromic Substring

コメント