LeetCode-Palindromic Substrings
题目描述
这是第647道题目：Palindromic Substrings
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:
代码语言：txt复制Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".Example 2:
代码语言：txt复制Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".题目要求是需要计算出给定字符串中所有回文子串的个数（单个字符也算一个回文子串，不同索引位置的相同内容的回文子串也算不同的回文）
思路分析
有两种思路：一种是采用动态规划的方法；另一种是采用中心扩散的方法。
- 动态规划
如果用dp[i][j]表示从第i个字符到第j个字符是不是回文子串，s表示给定字符串，则有
dp[i][j]= (s[i] == s[j]) && (i - j < 2) （这里表示的是子串是一个字符，两个字符的情形）
dp[i][j]= (s[i] == s[j]) && (dp[i 1][j -1] ) （这里表示的是除了前面两种情形之外的情形）
注：三个字符串的情形既可以归类到第一种情况（如果归类到第一种情况，则条件需要变为i - j < 3），也可以归类到第二种情形
- 中心扩散
扩散法假定一个中心，然后采用左右两个指针同时向两边走来判断是不是回文。
注：中心扩散法需要区分回文子串中的字符个数是奇数和偶数两种情况。
C 实现
- 动态规划
class Solution {
public:
int countSubstrings(string s) {
const int N = static_cast<int>(s.size()); // 如果不强转就会超时，好奇怪
int count = 0;
// 下面这一行换成原生数组也是可以的int dp[N][N]
vector<vector<bool>> dp(N, vector<bool>(N));
// 从后面遍历是为了让求dp[i][j]的时候dp[i 1][j - 1]是已经计算过的
for (auto i = N - 1; i >= 0; --i) {
for (auto j = i; j < N; j) {
// (j - i < 2)包含了两种情况，使得dp[i 1][j - 1]可以包含剩下的所有情况
dp[i][j] = (s[i] == s[j]) && ((j - i < 2) || dp[i 1][j - 1]);
if (dp[i][j]) count ;
}
}
return count;
}
};在使用C 实现的时候，我发现一些有意思的现象：
- 在第四行
s.size()的返回类型本来是size_t，但是如果直接使用size_t的话，运行直接超时。我强制转换为int以后就可以通过测试。有童鞋能帮我解答一下疑惑吗？
