45/300
回文子串 给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。 示例 1: 输入: “abc” 输出: 3 解释: 三个回文子串: “a”, “b”, “c”. 示例 2: 输入: “aaa” 输出: 6 说明: 6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”. 注意: 输入的字符串长度不会超过1000。动态规划类型，第三道： 举例X属于未知数字。 ‘aXXb’肯定不是回文，如果是 ‘aXXa’ 呢？ 需要判断中间两位是不是回文，如果这个状态True/False已经被记录，可以直接调取。 同理，'aXb’肯定不是回文，‘aXa’ 则需调取X的状态。 再小一点‘ab’，‘aa’我们可以直接判断True or False。 最小到‘a’，‘b’直接记录True
我们把思路从底往上实现： ‘abca’
0 1 2 3 [ a, b, c, a], 0 [a, T, F, F, F], 1 [b, , T, F, F], 2 [c, , , T, F], 3 [a, , , , T] class Solution: def countSubstrings(self, s): """ :type s: str :rtype: int """ if not s: return 0 n = len(s) #n*n的小本本准备好 memo = [[None]*n for _ in range(n)] count = 0 #遇True则+1 #记录'a','b' = True for i in range(n): memo[i][i] = True count += 1 for j in range(1,n): for i in range(j): # 'abcd' # j = 1, i = 0 [0][1]ab # j = 2, i = 0, 1 [0][2]ac [1][2]bc # j = 3, i = 0, 1, 2 [0][3]abcd [1][3]bcd [2][3]cd #'aa' 'aXa' if s[i] == s[j] and j-i <= 2: memo[i][j] = True count += 1 #'aXXa' 'aXXXa' elif s[i] == s[j] and j-i > 2: #调取状态 if memo[i+1][j-1]: memo[i][j] = True count += 1 else: memo[i][j] = False #'ab''aXb''aXXb'.. else: memo[i][j] = False return count但，从大佬处发现了更高效的办法！
画个思路丑图：‘abcded’
class Solution: def countSubstrings(self, s): """ :type s: str :rtype: int """ if not s: return 0 n = len(s) count = 0 for i in range(2*n-1): l = i//2；r = (i+1)//2 while l >= 0 and r < n and s[l] == s[r]: count += 1 l -= 1; r += 1 return count