Palindromic Substrings

https://leetcode.com/problems/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.

Thoughts

统计S中所有满足回文的子串个数。回文 + 统计个数，直观想法是用DP判断所有子串是否回文，global记录下结果。

利用回文的性质，对每个元素从两边拓展看能否组成回文。拓展的方式有长度为奇数和偶数两种。时间复杂度虽然没变，但实际基本不会每个子串都检查一遍，lc上时间beats 100%。空间复杂度也降到了O(1)。

Code

// @lc code=start
class Solution {
public:
    int countSubstrings(string s) {
        const int N = s.length();
        int res = 0;
        const auto ext = [&](string &s, int l, int r) {
            while (l >= 0 && r < N && s[l--] == s[r++]) {
                ++res;
            }
        };
        for (int i = 0; i < N; ++i) {
            ext(s, i, i);
            ext(s, i, i + 1);
        }
        return res; 
    }
};
// @lc code=end

/*
 * @lc app=leetcode id=647 lang=cpp
 *
 * [647] Palindromic Substrings
 */

// @lc code=start
class Solution {
public:
    int countSubstrings(string s) {
        const int N = s.length();
        vector<vector<bool>> dp(N, vector<bool>(N, false));
        int res = N;
        for (int i = 0; i < N; ++i) dp[i][i] = true;
        for (int i = N - 1; i >= 0; --i) {
            for (int j = i + 1; j < N; ++j) {
                if (s[i] == s[j] && (i == j - 1 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                    ++res;
                }
            }
        }
        return res; 
    }
};
// @lc code=end

Analysis

Errors:

1. corner cases

时间复杂度是两次O(n^2), 因为f是二维数组。