647. Palindromic Substrings -M

Given a string s, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

 

Example 1:

Input: s = "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

Input: s = "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

 

Constraints:

• 1 <= s.length <= 1000
• s consists of lowercase English letters.

A:

---------------遍历所有的奇数和偶数长度--------

class Solution {
public:
    int countSubstrings(string s) {
        // for odd length
        int count = 0, n = s.length();
        for (int i = 0; i < n; i++) {
            count++; // count this char only,
            int step = 1;
            while (i - step >= 0 && i + step < n &&
                   s[i - step] == s[i + step]) {
                count++;
                step++;
            }
        }
        // for even length
        int r, step;
        for (int l = 0; l < n - 1; l++) {
            r = l + 1;
            step = 0;
            while (l - step >= 0 && r + step < n &&
                   s[l - step] == s[r + step]) {
                count++;
                step++;
            }
        }
        return count;
    }
};

-------------上面的精简 代码-----------

class Solution {
public:
    int countSubstrings(string s) {        
        vector<pair<int, int> > V; // for all number of P
        for(int i=0;i< s.length() ;++i)  // search odd length
            V.push_back(make_pair(i,i));  // start and end, inclusive        
        
        for(int i=0;i+1< s.length();++i)  // search even length
            if(s[i] == s[i+1])                
                V.push_back(make_pair(i,i+1));  // start and end, inclusive
                
        for(int i =0;i<V.size();++i)
            if(V[i].first>0 and V[i].second+1< s.length() and s[V[i].first-1] == s[V[i].second+1])
                V.push_back(make_pair(V[i].first-1, V[i].second+1));
        return V.size();
    }
};