回文子串的数量

package main
//import "fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param str string字符串 
 * @return int整型
*/
func Substrings( str string ) int {
    ans:=0
    for i:=0;i<len(str);i++{
        for j:=i+1;j<=len(str);j++{
            if check(str[i:j]){
                ans++
            }
        }
    }
    return ans
}

func check(s string)bool{
    i,j:=0,len(s)-1
    for i<j{
        if s[i]!=s[j]{
            return false
        }
        i++
        j--
    }
    return true
}

# -*- coding: utf-8 -*-


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param str string字符串
# @return int整型
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/3e8b48c812864b0eabba0b8b25867738?tpId=196&tqId=40443&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=
    算法：
        设dp[i][j]表示字符串str的子串str[i: j+1]是否为回文串，本题要求计算有多个回文子串，也就是统计dp[i][j] = True的数量
        状态转移方程：
            若i = j：
                dp[i][j] = True
            若str[i] = str[j]：
                若i + 1 = j：
                    dp[i][j] = True
                否则：
                    dp[i][j] = dp[i + 1][j - 1]
    复杂度：
        时间复杂度：O(n^2), n为字符串str的长度
        空间复杂度：O(n^2)
    """

    def Substrings(self, str):
        # write code here
        n = len(str)

        dp = [[False] * n for _ in range(n)]

        res = 0
        for i in range(n - 1, -1, -1):
            for j in range(i, n):
                if i == j:
                    dp[i][j] = True
                elif str[i] == str[j]:
                    if i + 1 == j:
                        dp[i][j] = True
                    else:
                        dp[i][j] = dp[i + 1][j - 1]
                if dp[i][j] == True:
                    res += 1
        return res


if __name__ == "__main__":
    sol = Solution()

    # str = "nowcoder"

    str = "nnn"

    res = sol.Substrings(str)

    print res

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return int整型
     */
    int Substrings(string str) {
        int n = str.size();
        int res=n;
        if(n<2) return n;
        vector<vector<int>>dp(n,vector<int>(n));
        //base case
        for(int i=0;i<n;i++){
            dp[i][i]=1;
        }
        for(int i=n-1;i>=0;i--){
            for(int j=i+1;j<n;j++){
                if(str[i]==str[j]){
                    if(j-i<3){
                        dp[i][j]=1;
                        res++;
                    }else{
                        if(dp[i+1][j-1]){
                            dp[i][j]=1;
                            res++;
                        }
                    }
                }
            }
        }
        return res;
    }
};