647. Palindromic Substrings -M

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:

1. The input string length won't exceed 1000.

A:

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

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

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

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();
    }
};