个人技术分享

647. 回文子串

题目链接：647. 回文子串

代码如下：

class Solution 
{
public:
    int countSubstrings(string s) 
    {
        int res=0;
        //布尔类型的dp[i][j]:表示区间范围[i,j](注意是左闭右闭)的子串是否是回文子串
        vector<vector<bool>> dp(s.size(),vector<bool>(s.size(),false));
        for(int i=s.size()-1;i>=0;i--)
        {
            for(int j=i;j<s.size();j++)
            {
                
                if(s[i]==s[j])
                {
                    //情况一:下标i与j相同,同一个字符例如a,当然是回文子串
                    //情况二:下标i与j相差为1,例如aa,也是回文子串
                    if(j-i<=1)
                    {
                        res++;
                        dp[i][j]=true;
                    }
                    // 情况三:下标i与j相差大于1的时候,这个区间是不是回文就看dp[i+1][j-1]是否为true
                    else if(dp[i+1][j-1])
                    {
                        res++;
                        dp[i][j]=true;
                    }
                }
            }
        }
        return res;
    }
};