LeetCode: 647. Palindromic Substrings

发表于 | 分类于

题目描述

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:

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

Example 2:

1
2
3
Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

这题的第一反应就是用动态规划做。dp[i][j]表示从s[i]-s[j]的字符串是否为回文，如果为回文，则为1，反之0.

状态转移表达式为：

初始化为对任何i，$dp[i][i] =1$。最后，只需要计算出dp中有多少个1即可。

代码实现

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
class Solution {
public:
    int countSubstrings(string s) {
        int result = 0;
        vector<vector<int>> dp(s.length(), vector<int>(s.length()));
        for (int i=0; i<s.length(); i++) {
            dp[i][i] = 1;
            result += 1;
        }
        for (int j=1; j < s.length(); j++) {
            for (int i=0; i<s.length(); i++) {
                if (i+j >= s.length())
                    break;
                if (j == 1 && s[i] == s[i+j]) {
                    dp[i][i+j] = 1;
                    result += 1;
                } else if (dp[i+1][i+j-1] == 1 && s[i] == s[i+j]) {
                    dp[i][i+j] = 1;
                    result += 1;
                }
            }
        }
        return result;
    }
};