647. Palindromic Substrings

Posted on Edited on In

647. Palindromic Substrings

Description

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:

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

Example 2:

1
2
3
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.

Hints/Notes

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    vector<vector<int>> dp;

    int countSubstrings(string s) {
        int n = s.size();
        dp.resize(n, vector<int>(n, -1));
        int res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (isParlindromic(i, j, s)) {
                    res++;
                }
            }
        }
        return res;
    }

    bool isParlindromic(int i, int j, string& s) {
        if (i >= j) {
            return true;
        }
        if (dp[i][j] != -1) {
            return dp[i][j];
        }
        int& res = dp[i][j];
        if (s[i] != s[j]) {
            res = false;
            return res;
        }
        res = isParlindromic(i + 1, j - 1, s);
        return res;
    }
};