C++回文子字符串问题怎么解决

这篇文章主要介绍“C++回文子字符串问题怎么解决”，在日常操作中，相信很多人在C++回文子字符串问题怎么解决问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”C++回文子字符串问题怎么解决”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！

Example 1:

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

Example 2:

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

Note:

The input string length won"t exceed 1000.

解法一：

class Solution {
public:
    int countSubstrings(string s) {
        if (s.empty()) return 0;
        int n = s.size(), res = 0;
        for (int i = 0; i < n; ++i) {
            helper(s, i, i, res);
            helper(s, i, i + 1, res);
        }
        return res;
    }
    void helper(string s, int i, int j, int& res) {
        while (i >= 0 && j < s.size() && s[i] == s[j]) {
            --i; ++j; ++res;
        }
    }
};

在刚开始的时候博主提到了自己写的 DP 的方法比较复杂，为什么呢，因为博主的 dp[i][j] 定义的是范围 [i, j] 之间的子字符串的个数，这样其实还需要一个二维数组来记录子字符串 [i, j] 是否是回文串，那还不如直接就将 dp[i][j] 定义成子字符串 [i, j] 是否是回文串就行了，然后i从 n-1 往0遍历，j从i往 n-1 遍历，然后看 s[i] 和 s[j] 是否相等，这时候需要留意一下，有了 s[i] 和 s[j] 相等这个条件后，i和j的位置关系很重要，如果i和j相等了，则 dp[i][j] 肯定是 true；如果i和j是相邻的，那么 dp[i][j] 也是 true；如果i和j中间只有一个字符，那么 dp[i][j] 还是 true；如果中间有多余一个字符存在，则需要看 dp[i+1][j-1] 是否为 true，若为 true，那么 dp[i][j] 就是 true。赋值 dp[i][j] 后，如果其为 true，结果 res 自增1，参见代码如下：

解法二：

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size(), res = 0;
        vector<vector<bool>> dp(n, vector<bool>(n));
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i; j < n; ++j) {
                dp[i][j] = (s[i] == s[j]) && (j - i <= 2 || dp[i + 1][j - 1]);
                if (dp[i][j]) ++res;
            }
        }
        return res;
    }
};

到此，关于“C++回文子字符串问题怎么解决”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注亿速云网站，小编会继续努力为大家带来更多实用的文章！