647. Palindromic Substrings

Leetcode link

解题思路——回文特性

题目要求我们求一个字符串中回文子字符串的个数

首先我们分析一下要达成回文有哪些可能：

• aba 形式：也就是由奇数个字符组成，除了中间的那个之外其他的两两相同
• aa 形式：由偶数个字符组成，两两相同

至此，我们可以通过遍历输入的字符串并分别判断以上两种可能性来计算回文子字符串的个数

C++

class Solution {
public:
    int countSubstrings(string s) {
        int res = 0;

        for(int i = 0;i<s.size();i++) {
            // 回文字符串长度是奇数
            int left = i, right = i;
            while(left>=0 && right <s.size() && s[left] == s[right]) {
                res++;
                left--;
                right++;
            }

            // 回文字符串长度是偶数
            left = i;
            right = i+1;
            while(left>=0 && right <s.size() && s[left] == s[right]) {
                res++;
                left--;
                right++;
            }
        }
        return res;
    }
};

Javascript

var countSubstrings = function(s) {
    let res = 0;
    for(let i=0;i<s.length;i++) {
        // 回文字符串长度是奇数
        let left = i, right = i;
        while (left >=0 && right <s.length && s[left] === s[right]) {
            res++;
            left--;
            right++;
        }

        // 回文字符串长度是偶数
        left = i;
        right = i+1;
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            res++;
            left--;
            right++;
        }
    }
    return res;
};

解题思路——DP

这题也可以用动态规划来解

首先我们把二维数组 dp[i][j] 定义为下标从 i 到 j 的字符串是否能构成回文

接下来，我们使用两个指针 i 跟 j，来遍历字符串

什么情况会构成回文呢？首先 s[i] == s[j] 是所有的大前提，满足这个前提之下有三种可能：

• i 跟 j 中间只有一个字符
• i 跟 j 是相邻的
• dp[i+1][j-1] 能构成回文

详情看代码：

C++

class Solution {
public:
    int countSubstrings(string s) {
        int res = 0;
        int len = s.size();
        vector<vector<bool>> dp(len, vector<bool>(len, false));

        for(int i = len-1;i>=0;i--) {
            for(int j = i;j<len;j++) {
                dp[i][j] = s[i] == s[j] && (j-i <= 2 || dp[i+1][j-1]);
                if(dp[i][j]) {
                    res++;
                }
            }
        }
        return res;
    }
};

Javascript

var countSubstrings = function(s) {
    let res = 0;
    let len = s.length;
    let dp = new Array(len);
    for(let i=0;i<len;i++) {
        dp[i] = new Array(len).fill(false);
    }

    for(let i=len-1;i>=0;i--) {
        for(let j = i;j<len;j++) {
            dp[i][j] = s[i] == s[j] && (j-i <= 2 || dp[i+1][j-1]);
            if(dp[i][j]) {
                res++;
            }
        }
     }

    return res;
};