回文子串的数量

# -*- 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