C++ Solution, 9ms, O(n) space & O(n^2) time


  • 0
    R
    int countSubstrings(string s) {
            int n = s.size(), ret = n;
            if (s.size() <= 1) return ret;
            // dp[len][i] indicates when s[i] or s[i],s[i+1] is the center of a palindrome
            // since we only need the last and current of odd and even length, mod 4.
            vector<vector<bool>> dp(4, vector<bool>(n, 0));
            // init all 1 when len == 0 and when len == 1
            dp[0].assign(n, 1);
            dp[1].assign(n, 1);
            for (int len = 2; len <= n; ++len)
            {
                int off = (len - 1) / 2, even = (len+1)%2;
                dp[len%4].assign(n, 0);        // clear cur state.
                for (int i = off; i < n - off - even; ++i)
                {
                    if (dp[(len-2)%4][i] && s[i-off] == s[i + even + off])
                    {
                        dp[len%4][i] = 1;
                        ++ret;
                    }
                }
            }
            return ret;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.