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遍歷整個(gè)串,以i為基準(zhǔn)向兩側(cè)移動(dòng)j位,比較兩側(cè)字符是否相等,為了保證這個(gè),用for循環(huán).
分兩種情況:
1.若回文串長(zhǎng)度為奇數(shù),則要使s[i-j, ... , i, ..., i+j]為回文串
2.若回文串長(zhǎng)度為偶數(shù),則要使s[i-1-j, ... , i-1, i, ..., i+j]為回文串(即i-1,i兩個(gè)基準(zhǔn))
同時(shí)還要保證下標(biāo)不越界.
int countSubstrings(string s) {
int count = 0; //計(jì)數(shù)
int n = s.size();
for (int i = 0; i < n; i++) { //遍歷整個(gè)串一次
for (int j = 0; i-j >= 0 && i+j < n && s[i-j] == s[i+j]; j++) //檢查回文長(zhǎng)度奇數(shù)情況
count++;
for (int j = 0; i-1-j >= 0 && i+j < n && s[i-1-j] == s[i+j]; j++) //檢查偶數(shù)情況
count++;
}
return count;
}
