647.回文子串

• • • 题目
    • 思路
    • 代码
    • 运行结果
    • 总结

'''
Description: 647.回文子串
Autor: 365JHWZGo
Date: 2021-12-23 18:52:54
LastEditors: 365JHWZGo
LastEditTime: 2021-12-23 20:08:16
'''

直观解题思路：
我的直觉是控制头部和尾部，那么就用一个二维数组分别代表头和尾，然后对角线肯定都是回文，那么就只需要判断从对角线以后的剩余部分。

一开始，我以为是从上到下，从左到右依次遍历，但是我发现这样的话无法判断间隔大于1的回文，如“aba”，因为当s[i]==s[j]时，即首和尾相等，此时应该判断的是dp[i+1][j-1]，即他俩中间的部分是否为回文。

所以此时可以肯定的是倒叙遍历，写完代码后进行测试验证，发现这种还是右缺陷，它无法判断像“aa"这种，因为它没有中间部分，所以对于它而言，我们只需要进行单独判断，即当j-1 ==i时，dp[i][j]=dp[i][j-1]。

此时就可以很好的解决问题了！

思路：
1.确定dp数组以及下标含义
    dp[i][j]代表判断子串s[i:j+1]是否为回文
 2.确定递推公式
     头尾相等时
         情况一:头尾之间有子串
             dp[i][j] = dp[i+1][j-1]
         情况二:头尾之间无子串
             dp[i][j] = dp[i][j-1]
 3.初始化dp数组
     对角线赋值为1
 4.确定遍历顺序
     外循环从后往前
     内循环从前往后
 5.举例推导
     s="abcbaa"
     dp
     [[1, 0, 0, 0, 1, 0], [0, 1, 0, 1, 0, 0], [0, 0, 1, 0, 0, 0], [0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 1, 1], [0, 0, 0, 0, 0, 1]]

class Solution(object):
    def countSubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """
        res = 0
        dp = [[0 for _ in range(len(s))]for _ in range(len(s))]
        for i in range(len(s)-1,-1,-1):
            for j in range(i,len(s)):
                if i == j:
                    dp[i][j] = 1
                    continue
                if j-1 == i and s[i] == s[j]:
                    dp[i][j] = dp[i][j-1]
                    continue
                if s[i] == s[j]:
                    dp[i][j] = dp[i+1][j-1]
            res += sum(dp[i])
        # print(dp)
        return res

这道题还是考验一定思维能力的，多思考，多进步！