647. 回文子串

题目描述：

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。

示例1：

输入:"abc"
输出:3
解释:三个回文子串: "a", "b", "c".

示例2：

输入:"aaa"
输出:6
说明:6个回文子串: "a", "a", "a", "aa", "aa", "aaa".

方法1：动态规划

本题可使用动态规划方法来解决。

设字符串长度为n，则新建布尔类型数组dp[n][n]来保存相应位置是否是回文字符串。其中dp[i][j]代表字符串从第i个字符到第j个字符组成的子串是否为回文字符串。

当i==j时，显然有dp[i][j] = true.

当i!=j时，则有

这是因为若i到j组成的子串为回文字符串时，其两端加上相同的字符仍为回文字符串。
在处理完所有子串后，对回文字符串进行统计即可。
具体代码如下：

 int countSubstrings(string s) {
        int n = s.length();
        vector<bool> t(n,false);
        vector<vector<bool>> dp(n,t);
        int res = 0;
        for (int j = 0; j < n; j++) {
            for (int i = 0; i <= j; i++) {
                if (i == j) {
                    dp[i][j] = true;
                } else {
                    dp[i][j] = s[i] == s[j] && (j - i <= 1 || dp[i + 1][j - 1]);
                }
            }
        }
        for(int i=0;i<n;i++)
        {
            for(int j=i;j<n;j++)
            {
                if(dp[i][j])
                {
                    res++;
                }
            }
        }
        return res;
    }

其中要注意i和j的顺序，由于在计算dp[i][j]时，需要dp[i+1][j-1]的值，则必须保证当计算dp[i][j]时，其左下侧的数值已经计算完毕。因此应按列进行计算。

方法二：奇偶扩展

回文字符串可以分为长度为奇数和长度为偶数2种情况。
当长度为奇数时，字符串由中心的一个字符向前后扩展，若前后字符串相同，则其扩展的字符串仍为回文字符串。
当长度为偶数时，字符串由两个相同的连续字符向前后扩展，若前后字符串相同，则其扩展的字符串仍为回文字符串。

int countSubstrings(string s) {
       int n = s.length();
       int res = 0;
       for(int i=0;i<n;i++)
       {
           int start = i,end = i;
           while(start >= 0 && end < n)
           {
               if(s[start] == s[end])
               {
                   res++;
                   start--;
                   end++;
               }
               else
               {
                   break;
               }
           }
           start = i;
           end = i + 1;
           while(start >= 0 && end < n)
           {
               if(s[start] == s[end])
               {
                   res++;
                   start--;
                   end++;
               }
               else
               {
                   break;
               }
           }
       }
       return res;
   }