力扣山的回文子串解析 代码随想录

回文子串是指正向和反向读取都相同的字符串片段。解决回文子串的问题通常有几种方法，其中一种常见的方法是使用动态规划。

以下是一种基于动态规划的解法，使用一个二维数组dp来记录子串是否为回文。

def countSubstrings(s):
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    count = 0

    # 初始化长度为1和2的回文子串
    for i in range(n):
        dp[i][i] = True
        count += 1

    for i in range(n - 1, -1, -1):
        for j in range(i + 1, n):
            # 判断当前子串是否为回文
            if s[i] == s[j]:
                # 如果子串长度小于等于2，则一定是回文
                if j - i <= 2:
                    dp[i][j] = True
                # 如果子串长度大于2，则看去掉首尾字符后的子串是否为回文
                else:
                    dp[i][j] = dp[i + 1][j - 1]

            # 如果当前子串为回文，则计数加1
            if dp[i][j]:
                count += 1

    return count

这段代码的思路是，首先初始化长度为1和2的回文子串，然后从字符串末尾开始遍历，逐个判断子串是否为回文。如果当前子串是回文，则计数加1。

该解法的时间复杂度为O(n^2)，空间复杂度为O(n^2)，其中n为字符串的长度。