【算法挨揍日记】day34——647. 回文子串、5. 最长回文子串

647. 回文子串?

647.?回文子串

题目描述：

给你一个字符串?s?，请你统计并返回这个字符串中?回文子串?的数目。

回文字符串?是正着读和倒过来读一样的字符串。

子字符串?是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

解题思路：

?解题代码：

class Solution {
public:
    int countSubstrings(string s) {
        int n=s.size();
        vector<vector<bool>>dp(n,vector(n,false));
        for(int i=n-1;i>=0;i--)
        {
            for(int j=i;j<n;j++)
            {
                if(s[i]==s[j])
                {
                    if(i==j)dp[i][j]=true;
                    else if(i+1==j)dp[i][j]=true;
                    else dp[i][j]=dp[i+1][j-1];
                }
            }
        }
        int ret=0;
        for(int i=0;i<n;i++)
        {
            for(int j=i;j<n;j++)
            {
                if(dp[i][j]==true)
                ret++;
            }
        }
        return ret;
    }
};

5. 最长回文子串?

5.?最长回文子串

题目描述：

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

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

?解题思路：

647.?回文子串https://leetcode.cn/problems/palindromic-substrings/

在647题的基础上遍历所有dp表中为true的初始位置和长度

解题代码：

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