美文网首页LeetCode
647. 回文子串

647. 回文子串

作者: cptn3m0 | 来源:发表于2019-03-17 13:56 被阅读1次

    这道题目和求解最长回文子串的题目是一样的框架结构, 不同的地方在于这到题目统计的是总数.

    class Solution(object):
        def countSubstrings(self, s):
            """
            :type s: str
            :rtype: int
            """
            
            # 这个题目和最长回文子串是一样的题目类型
            # 区别在于最长回文子串求解的最长的回文
            # 这套题目要求的是所有的回文子串的数目
            n = len(s)
            dp = [[False]*n for _ in range(n)]
            
    
            ret_count = 0
            # 初始化1, 对应于奇数
            for i in range(n):
                dp[i][i] = True
                # 统计长度为1的回文子串的数目
                ret_count +=1
                
            # 初始化2, 对应于偶数
            for i in range(1, n):
                if s[i-1] ==  s[i]:
                    dp[i-1][i] = True
                    # 统计长度为2的回文子串的数目
                    ret_count+=1
            # 从 strlen == 3 开始递推
            for strlen in range(3,n+1):
                for i in range(0,n-strlen+1):
                    j = i+strlen -1
                    
                    if s[i] ==s[j] and dp[i+1][j-1] == True:
                        dp[i][j] = True
                        # 统计长度从3开始的回文子串的数目
                        ret_count +=1
            
            return ret_count
    

    相关文章

      网友评论

        本文标题:647. 回文子串

        本文链接:https://www.haomeiwen.com/subject/mjhumqtx.html