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.
思路1:暴力解法,用i遍历整个串,以i为基准向两侧移动j位,比较两侧字符是否相等,为了保证这个,用for循环.
分两种情况:
1.若回文串长度为奇数,则要使s[i-j, ... , i, ..., i+j]为回文串
2.若回文串长度为偶数,则要使s[i-1-j, ... , i-1, i, ..., i+j]为回文串(即i-1,i两个基准)
同时还要保证下标不越界.
int countSubstrings(string s) {
int count = 0; //计数
int n = s.size();
for (int i = 0; i < n; i++) { //遍历整个串一次
for (int j = 0; i-j >= 0 && i+j < n && s[i-j] == s[i+j]; j++) //检查回文长度奇数情况
count++;
for (int j = 0; i-1-j >= 0 && i+j < n && s[i-1-j] == s[i+j]; j++) //检查偶数情况
count++;
}
return count;
}
