647. 回文子串

https://leetcode-cn.com/problems/palindromic-substrings/

解法一：暴力

用i遍历整个串,以i为基准向两侧移动j位,比较两侧字符是否相等,为了保证这个,用for循环. 分两种情况:

1.若回文串长度为奇数,则要使s[i-j, ... , i, ..., i+j]为回文串

2.若回文串长度为偶数,则要使s[i-1-j, ... , i-1, i, ..., i+j]为回文串(即i-1,i两个基准) 同时还要保证下标不越界.

class Solution {
public:
    int countSubstrings(string s) {
        int count = 0;  //计数
        int n = s.size();
        for (int i = 0; i < n; i++) {  //遍历整个串一次
            for (int j = 0; i-j >= 0 && i+j < n && s[i-j] == s[i+j]; j++) //检查回文长度奇数情况
                count++;  
            for (int j = 0; i-1-j >= 0 && i+j < n && s[i-1-j] == s[i+j]; j++)  //检查偶数情况
                count++;
        }
        return count;
    }
};

解法二：dp

参照5.最长回文子串

构建dp矩阵，然后遍历dp统计True的数量即可。

class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        dp = [[0 for i in range(n)] for i in range(n)]  #二维数组创建
        for i in range(n-1, -1, -1):
            for j in range(i, n):
                dp[i][j] = (s[i] == s[j] and (j - i < 3 or dp[i+1][j-1]))
        res = 0
        for i in range(n):
            res += dp[i].count(True)
        return res