Palindromic Substrings

Description

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.

Solutions

My solution

The number of palindromic substrings in s[0..i] is the number of palindromic substrings in s[0..i-1] + the number of palindromic substrings ending with s[i].

A substring s[i..j] is palindromic if and only if s[i] == s[j] and s[i+1..j-1] is palindromic.

class Solution {
    public:
    int countSubstrings(string s) {
        int n = s.size();
        // dp[i][j] == true iff s[j..i] is palindromic
        vector<vector<bool>> dp(n, vector<bool>(n));
        int count = 0;
        for(int i = 0; i < n; ++i){
            for(int j = 0; j <= i; ++j){
                dp[i][j] = s[i] == s[j] && (i - j < 2 || dp[i - 1][j + 1]);
                if(dp[i][j]) ++count;
            }
        }
        return count;
    }
};

Optimal solution

(Not a dynamic programming solution)

class Solution {
public:
    int countSubstrings(string s) {
        int count = 0;
        for(int i = 0; i < s.size(); ++i){
            count += countPalindromes(s, i, i);
            count += countPalindromes(s, i, i + 1);
        }
        return count;
    }

    // count the number of palindromes with center s[l..r]
    int countPalindromes(string &s, int l, int r){
        int count = 0;
        while(l >= 0 && r < s.size() && s[l] == s[r]){
            ++count;
            --l;
            ++r;
        }
        return count;
    }
};