本文共 1175 字，大约阅读时间需要 3 分钟。

题目：

Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Example 1:

Input: "abc" Output: 3 Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

Input: "aaa" Output: 6 Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Note:

The input string length won’t exceed 1000.

解释：

查找一个字符串中有多少个是回文的子字符串。 reuse之前的结果~ 从中间往两边走(使用中心向外拓展的方法) 假设当前位置i为回文的中心，那么回文中心有两种情况，即回文长度是奇数的情况或者回文长度是偶数的情况， 如果回文是奇数，left=i-1,right=i+1 如果回文是偶数，left=i,right=i+1 i的取值范围是0~n-1 python代码：

class Solution(object):    def countSubstrings(self, s):        """        :type s: str        :rtype: int        """        len_s=len(s)        result=0        for i in xrange(len_s):            result+=1            #回文长度是奇数的情况：            left=i-1            right=i+1            while left>=0 and right
   
    =0 and right
   

c++代码：

class Solution {
   public:    int countSubstrings(string s) {
           int len_s=s.size();        int result=0;        for(int i=0;i
   
    =0 && right
    
     =0  && right
    
   

总结：

转载地址：http://gglcn.baihongyu.com/