C++如何拆分回文串

这篇“C++如何拆分回文串”文章的知识点大部分人都不太理解,所以小编给大家总结了以下内容,内容详细,步骤清晰,具有一定的借鉴价值,希望大家阅读完这篇文章能有所收获,下面我们一起来看看这篇“C++如何拆分回文串”文章吧。

10年积累的成都做网站、成都网站制作、成都外贸网站建设经验,可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你,你也不认识我。但先网站策划后付款的网站建设流程,更有边坝免费网站建设让你可以放心的选择与我们合作。

解法一:

class Solution {
public:
    int minCut(string s) {
        if (s.empty()) return 0;
        int n = s.size();
        vector> p(n, vector(n));
        vector dp(n);
        for (int i = 0; i < n; ++i) {
            dp[i] = i;
            for (int j = 0; j <= i; ++j) {
                if (s[i] == s[j] && (i - j < 2 || p[j + 1][i - 1])) {
                    p[j][i] = true;
                    dp[i] = (j == 0) ? 0 : min(dp[i], dp[j - 1] + 1);
                }
            }
        }
        return dp[n - 1];
    }
};

我们也可以反向推,这里的dp数组的定义就刚好跟前面反过来了,dp[i] 表示区间 [i, n-1] 内的最小分割数,所以最终只需要返回 dp[0] 就是区间 [0, n-1] 内的最喜哦啊分割数了,极为所求。然后每次初始化 dp[i] 为 n-1-i 即可,j 的更新范围是 [i, n),此时我们就只需要用 1 + dp[j+1] 来更新 dp[i] 了,为了防止越界,需要对 j == n-1 的情况单独处理一下,整个思想跟上面的解法一模一样,请参见之前的讲解。

解法二:

class Solution {
public:
    int minCut(string s) {
        if (s.empty()) return 0;
        int n = s.size();
        vector> p(n, vector(n));
        vector dp(n);
        for (int i = n - 1; i >= 0; --i) {
            dp[i] = n - i - 1;
            for (int j = i; j < n; ++j) {
                if (s[i] == s[j] && (j - i <= 1 || p[i + 1][j - 1])) {
                    p[i][j] = true;
                    dp[i] = (j == n - 1) ? 0 : min(dp[i], dp[j + 1] + 1);
                }
            }
        }
        return dp[0];
    }
};

下面这种解法是论坛上的高分解法,没用使用判断区间 [i, j] 内是否为回文串的二维dp数组,节省了空间。但写法上比之前的解法稍微有些凌乱,也算是个 trade-off 吧。这里还是用的一维dp数组,不过大小初始化为了 n+1,这样其定义就稍稍发生了些变化,dp[i] 表示由s串中前 i 个字母组成的子串的最小分割数,这样 dp[n] 极为最终所求。接下来就要找状态转移方程了。这道题的更新方式比较特别,跟之前的都不一样,之前遍历 i 的时候,都是更新的 dp[i],这道题更新的却是 dp[i+len+1] 和 dp[i+len+2],其中 len 是以i为中心,总长度为 2*len + 1 的回文串,比如 bob,此时 i=1,len=1,或者是i为中心之一,总长度为 2*len + 2 的回文串,比如 noon,此时 i=1,len=1。中间两个for循环就是分别更新以 i 为中心且长度为 2*len + 1 的奇数回文串,和以 i 为中心之一且长度为 2*len + 2 的偶数回文串的。i-len 正好是奇数或者偶数回文串的起始位置,由于我们定义的 dp[i] 是区间 [0, i-1] 的最小分割数,所以 dp[i-len] 就是区间 [0, i-len-1] 范围内的最小分割数,那么加上奇数回文串长度 2*len + 1,此时整个区间为 [0, i+len],即需要更新 dp[i+len+1]。如果是加上偶数回文串的长度 2*len + 2,那么整个区间为 [0, i+len+1],即需要更新 dp[i+len+2]。这就是分奇偶的状态转移方程,参见代码如下:

解法三:

class Solution {
public:
    int minCut(string s) {
        if (s.empty()) return 0;
        int n = s.size();
        vector dp(n + 1, INT_MAX);
        dp[0] = -1;
        for (int i = 0; i < n; ++i) {
            for (int len = 0; i - len >= 0 && i + len < n && s[i - len] == s[i + len]; ++len) {
                dp[i + len + 1] = min(dp[i + len + 1], 1 + dp[i - len]);
            }
            for (int len = 0; i - len >= 0 && i + len + 1 < n && s[i - len] == s[i + len + 1]; ++len) {
                dp[i + len + 2] = min(dp[i + len + 2], 1 + dp[i - len]);
            }
        }
        return dp[n];
    }
};

以上就是关于“C++如何拆分回文串”这篇文章的内容,相信大家都有了一定的了解,希望小编分享的内容对大家有帮助,若想了解更多相关的知识内容,请关注创新互联行业资讯频道。


网页题目:C++如何拆分回文串
本文网址:http://bzwzjz.com/article/gpjsgd.html

其他资讯

Copyright © 2007-2020 广东宝晨空调科技有限公司 All Rights Reserved 粤ICP备2022107769号
友情链接: 网站制作公司 成都定制网站建设 定制网站建设 LED网站设计方案 成都网站建设 重庆网站建设 企业网站建设公司 app网站建设 营销型网站建设 重庆电商网站建设 成都做网站建设公司 成都网站建设公司 成都企业网站建设公司 成都网站制作 重庆外贸网站建设 成都网站设计 广安网站设计 网站制作 高端品牌网站建设 响应式网站设计 泸州网站建设 网站建设公司