189 8069 5689

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

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

创新互联建站-专业网站定制、快速模板网站建设、高性价比静宁网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式静宁网站制作公司更省心,省钱,快速模板网站建设找我们,业务覆盖静宁地区。费用合理售后完善,10余年实体公司更值得信赖。

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> dp(n, vector(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++回文子字符串问题怎么解决”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注创新互联网站,小编会继续努力为大家带来更多实用的文章!


网页名称:C++回文子字符串问题怎么解决
新闻来源:http://cdxtjz.cn/article/gjjsig.html

其他资讯