647.palindromic-substrings.md

647. 回文子串
648. 描述
     • 给定一个字符串，你的任务是计算这个字符串中，回文子串有多少个。
     • 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
649. 示例
     • 示例 1： 输入："abc" 输出：3 解释：三个回文子串: "a", "b", "c"
     • 示例 2： 输入："aaa" 输出：6 解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
650. 思路：中心扩展法
     • 时间复杂度：O(n^2)
     • 空间复杂度：O(1)
651. 实现

     class Solution {
         public:    
             // 中心扩展法
             //以s[l], s[r]为中心向两侧扩展，返回当前 回文子串 个数
             int cur_len_Palindromic(string s, int l, int r)
             {
                 int count=0;
                 while(l>=0 && r<s.size() && s[l]==s[r])
                 {            
                     l--;
                     r++;
                     count++;
                 }
                 return count;
             } 
             int countSubstrings(string s) {
                 if(s.size()==0)
                     return 0;
     
                 int i, res=0;
                 for(i=0; i<s.size(); i++)
                 {
                     //以s[i]为中心向两侧扩展，得到 回文子串 个数
                     //以s[i], s[i+1]为中心向两侧扩展，得到 回文子串 个数
                     res += ( cur_len_Palindromic(s,i,i) + cur_len_Palindromic(s,i,i+1) );                
                 }
                 return res;
             }              
         };