647. Palindromic Substrings

最大回文串
正好让我回顾一下DP，动态规划比较经典的题目

Output: 3
Explanation: Three palindromic strings: "a", "b", "c".
Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

总之就是一个线性规划的问题，注意递归条件：

if (s[start] = s[end] and (dp[start+1][end-1] or end-start<3)):
      dp[start][end] = 1

    def countSubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """
        count = 0
        l = len(s)
        dp = [[0 for i in range(l)]for i in range(l)]
        if len(s) == 0:
            return count
        for end in range(0,len(s)):
            dp[end][end] = 1
            count += 1
            for start in range(0,end):
                if s[start] == s[end] and (dp[start+1][end-1] or end-start<3):
                    dp[start][end] = 1
                    count += 1
        
        return count

另附一开始的办法，直接reverse翻转字符串比较，对的就+1，注意str没有reverse，直接用切片操作：

    def countSubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """
        count = 0
        str1 = ''
        str2 = ''
        if len(s) == 0:
            return count
        for i in range(0,len(s)):
            for j in range(i+1,len(s)+1):
                    str1 = s[i:j]
                    str2 = str1[::-1]
                    if str1 == str2:
                        count +=1
                    str1 = []
                    str2 = []
                
        return count