力扣第131题 分割回文串 c++ 回溯+简单 动态规划(是否为回文子串)

这篇具有很好参考价值的文章主要介绍了力扣第131题 分割回文串 c++ 回溯+简单 动态规划(是否为回文子串)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目

131. 分割回文串

中等

相关标签

字符串   动态规划   回溯

给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

示例 1:

输入:s = "aab"
输出:[["a","a","b"],["aa","b"]]

示例 2:

输入:s = "a"
输出:[["a"]]

提示:

  • 1 <= s.length <= 16
  • s 仅由小写英文字母组成

思路和解题方法一 回溯+判断

  1. ans 是一个二维向量,用于存储最终的结果。每个元素都是一个符合要求的回文字符串组合。

  2. path 是一个一维向量,用于存储当前的路径。它表示已经找到的符合要求的回文子串。

  3. backtrackint 是回溯函数,用于搜索并构建符合要求的回文字符串组合。它接收两个参数:字符串 s 和当前的索引 index

  4. backtrackint 中,首先判断是否遍历到字符串末尾。如果是,将当前路径添加到结果 ans 中,并返回。

  5. 然后,从当前位置 index 开始,通过一个循环遍历字符串。变量 i 表示循环的当前位置。

  6. 在循环中,通过调用 ifhuimen 函数判断从当前位置 indexi 是否是回文子串。如果是回文子串,则将该子串加入当前路径 path 中。

  7. 然后,递归调用 backtrackint 函数,传入新的起始位置 i + 1 ,继续处理剩余的部分。

  8. 在递归之后,需要进行回溯操作,即将当前路径 path 的最后一个元素移除,以便继续寻找其他可能的回文子串组合。

  9. 最后,调用 partition 函数,通过回溯函数 backtrackint 来搜索所有符合要求的回文字符串组合,并返回结果向量 ans

复杂度

        时间复杂度:

                O(2^n * n)

时间复杂度

  • 对于长度为 n 的字符串,最坏情况下可能有 2^(n-1) 种不同的回文子串组合。
  • 在回溯过程中,我们需要遍历所有可能的组合,每个组合都需要进行 O(n) 的操作来判断是否是回文子串。
  • 因此,回溯算法的时间复杂度为 O(2^n * n)。

        空间复杂度

                O(n^2)

空间复杂度:

  • 回溯算法消耗了大量的递归栈空间,最坏情况下需要 O(n) 的空间。
  • 另外,还需要额外的空间来储存存储中间结果的二维向量 ans 和存储当前路径的一维向量 path,因此空间复杂度为 O(n^2)。

c++ 代码一

class Solution {
public:
    vector<vector<string>> ans; // 存储结果的二维向量
    vector<string> path; // 存储当前路径的一维向量
    
    void backtrackint(string &s, int index) {
        if (index >= s.size()) { // 如果遍历到字符串末尾,将当前路径添加到结果中
            ans.push_back(path);
            return;
        }
        for (int i = index; i < s.size(); i++) { // 遍历字符串,从当前位置开始
            if (ifhuimen(s, index, i)) { // 判断从当前位置到 i 是否是回文子串
                string str = s.substr(index, i - index + 1); // 获取回文子串
                path.push_back(str); // 将回文子串加入当前路径
            } else {
                continue; // 如果不是回文子串,跳过当前位置
            }
            backtrackint(s, i + 1); // 递归处理剩余部分
            path.pop_back(); // 回溯,将当前路径的最后一个元素移除
        }
    }

    bool ifhuimen(string &s, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            if (s[i] != s[j]) {
                return false; // 判断是否为回文子串
            }
        }
        return true;
    }

    vector<vector<string>> partition(string s) {
        ans.clear(); // 清空结果向量
        path.clear(); // 清空路径向量
        backtrackint(s, 0); // 回溯搜索所有回文子串的组合
        return ans; // 返回结果向量
    }
};

思路和解题方法二 回溯+动态规划

  1. 首先,定义了私有变量 resultpathisPalindromeresult 是最终的分割结果,path 是存储已经回文的子串,isPalindrome 存储事先计算好的是否回文子串的结果。

  2. backtracking 函数中进行回溯操作。如果起始位置 startIndex 大于等于字符串 s 的大小,说明已经找到了一组分割方案,将当前的路径 path 加入到结果集 result 中,并返回。

  3. 接下来,从 startIndex 开始循环遍历字符串 s。如果从 startIndex 到当前位置 i 的子串是回文子串(根据事先计算好的 isPalindrome 布尔矩阵判断),则将该子串加入到路径 path 中,并递归地在其后面的位置继续寻找回文子串。

  4. 在回溯过程中,如果发现当前位置 istartIndex 的子串不是回文子串,直接跳过。如果是回文子串,继续调用 backtracking 函数,并将 i + 1 作为新的起始位置,寻找下一个回文子串。

  5. 在每一次递归返回之前,需要将当前已经添加到路径 path 中的子串弹出,以便进行下一次回溯。

  6. computePalindrome 函数用于计算字符串 s 中的回文子串。它通过动态规划的思想,从后向前依次计算字符串中的回文子串。具体做法是,首先遍历字符串中的每个字符,将单个字符视为回文子串;然后,对于长度为2的子串,如果两个字符相等,则它们是回文子串;最后,对于长度大于2的子串,如果首尾字符相等,并且去除首尾后的子串仍然是回文子串,那么它们也是回文子串。

  7. partition 函数是整个程序的入口。在开始分割之前,首先清空结果集 result 和路径 path。然后调用 computePalindrome 函数计算回文子串,并调用 backtracking 函数进行回溯查找分割方案。

  8. 最后,返回结果集 result,即可得到所有的分割方案。

复杂度 和上面一样

        时间复杂度:

                O(2^n * n)

        空间复杂度

                O(n^2)

c++ 代码二

class Solution {
private:
    vector<vector<string>> result;               // 存储最终的分割结果
    vector<string> path;                         // 存储已经回文的子串
    vector<vector<bool>> isPalindrome;           // 存储事先计算好的是否回文子串的结果

    void backtracking(const string& s, int startIndex) {
        // 如果起始位置已经大于s的大小,说明已经找到了一组分割方案了
        if (startIndex >= s.size()) {
            result.push_back(path);
            return;
        }

        for (int i = startIndex; i < s.size(); i++) {
            if (isPalindrome[startIndex][i]) {    // 是回文子串
                // 获取[startIndex,i]在s中的子串
                string str = s.substr(startIndex, i - startIndex + 1);
                path.push_back(str);
            } else {                                // 不是回文,跳过
                continue;
            }
            backtracking(s, i + 1);                 // 寻找i+1为起始位置的子串
            path.pop_back();                        // 回溯过程,弹出本次已经添加的子串
        }
    }

    void computePalindrome(const string& s) {
        // isPalindrome[i][j] 代表 s[i:j](双边包括)是否是回文字串 
        isPalindrome.resize(s.size(), vector<bool>(s.size(), false));  // 根据字符串s,刷新布尔矩阵的大小

        for (int i = s.size() - 1; i >= 0; i--) { 
            // 需要倒序计算,保证在i行时,i+1行已经计算好了
            for (int j = i; j < s.size(); j++) {
                if (j == i) {
                    isPalindrome[i][j] = true;
                } else if (j - i == 1) {
                    isPalindrome[i][j] = (s[i] == s[j]);
                } else {
                    isPalindrome[i][j] = (s[i] == s[j] && isPalindrome[i + 1][j - 1]);
                }
            }
        }
    }

public:
    vector<vector<string>> partition(string s) {
        result.clear();
        path.clear();
        computePalindrome(s);        // 计算是否回文子串
        backtracking(s, 0);          // 回溯得到分割结果
        return result;
    }
};

觉得有用的话可以点点赞,支持一下。

如果愿意的话关注一下。会对你有更多的帮助。

每天都会不定时更新哦  >人<  。文章来源地址https://www.toymoban.com/news/detail-724123.html

到了这里,关于力扣第131题 分割回文串 c++ 回溯+简单 动态规划(是否为回文子串)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 力扣第40题 组合总和 || c++ 回溯经典

    40. 组合总和 II 中等 相关标签 数组   回溯 给定一个候选人编号的集合  candidates  和一个目标数  target  ,找出  candidates  中所有可以使数字和为  target  的组合。 candidates  中的每个数字在每个组合中只能使用  一次  。 注意: 解集不能包含重复的组合。  示例 1: 示例

    2024年02月07日
    浏览(40)
  • 【Leetcode】 131. 分割回文串

    给你一个字符串 s ,请你将 s 分割成一些子串,使每个子串都是 回文串 。返回 s 所有可能的分割方案。 回文串 是正着读和反着读都一样的字符串。 示例 1: 输入 : s = \\\"aab\\\" 输出 : [[\\\"a\\\",\\\"a\\\",\\\"b\\\"],[\\\"aa\\\",\\\"b\\\"]] 示例 2 : 输入 : s = \\\"a\\\" 输出 : [[\\\"a\\\"]] 提示: s 仅由小写英文字母组成

    2024年02月07日
    浏览(39)
  • 【力扣】416. 分割等和子集 <动态规划、回溯>

    给你一个 只包含正整数的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。 示例 1: 输入:nums = [1,5,11,5] 输出:true 解释:数组可以分割成 [1, 5, 5] 和 [11] 。 示例 2: 输入:nums = [1,2,3,5] 输出:false 解释:数组不能分割成两个元素和

    2024年02月10日
    浏览(38)
  • 力扣第474题 一和零 c++ 动态规划 01背包

    474. 一和零 中等 相关标签 数组   字符串   动态规划 给你一个二进制字符串数组  strs  和两个整数  m  和  n  。 请你找出并返回  strs  的最大子集的长度,该子集中  最多  有  m  个  0  和  n  个  1  。 如果  x  的所有元素也是  y  的元素,集合  x  是集合  y

    2024年02月06日
    浏览(37)
  • 力扣第494题 目标和 c++ 动态规划 c++ 01背包 难~~

    494. 目标和 中等 相关标签 数组   动态规划   回溯 给你一个非负整数数组  nums  和一个整数  target  。 向数组中的每个整数前添加  \\\'+\\\'  或  \\\'-\\\'  ,然后串联起所有整数,可以构造一个  表达式  : 例如, nums = [2, 1]  ,可以在  2  之前添加  \\\'+\\\'  ,在  1  之前添加 

    2024年02月06日
    浏览(36)
  • 【刷题1】LeetCode 131. 分割回文串 java题解

    2024: 刚开始做leetcode hot100,查阅自己以前写的题解专栏,发现没有这一题,于是加上。可能leetcode100更新了吧。我看现在leetcode100官网的题目已经是分好类的了,以前我的题解帖子是自己手动分类整理的。

    2024年02月19日
    浏览(39)
  • 力扣第509题 斐波那契数 新手动态规划(推荐参考) c++

    509. 斐波那契数 简单 相关标签 递归   记忆化搜索   数学   动态规划 斐波那契数  (通常用  F(n)  表示)形成的序列称为  斐波那契数列  。该数列由  0  和  1  开始,后面的每一项数字都是前面两项数字的和。也就是: 给定  n  ,请计算  F(n)  。 示例 1: 示例 2:

    2024年02月07日
    浏览(47)
  • 力扣第1049题 最后一块石头的重量Il c++ 动态规划(01背包)

    1049. 最后一块石头的重量 II 中等 相关标签 有一堆石头,用整数数组  stones  表示。其中  stones[i]  表示第  i  块石头的重量。 每一回合,从中选出 任意两块石头 ,然后将它们一起粉碎。假设石头的重量分别为  x  和  y ,且  x = y 。那么粉碎的可能结果如下: 如果  x

    2024年02月06日
    浏览(43)
  • day27 | 39. 组合总和、 40.组合总和II、131.分割回文串

    目录: 39. 组合总和 给你一个  无重复元素  的整数数组  candidates  和一个目标整数  target  ,找出  candidates  中可以使数字和为目标数  target  的 所有 ** 不同组合  ,并以列表形式返回。你可以按  任意顺序  返回这些组合。 candidates  中的  同一个  数字可以  无限

    2024年02月10日
    浏览(40)
  • 力扣第96题 不同的二叉搜索树 c++ 二叉搜索树 动态规划 + 数学思维

    96. 不同的二叉搜索树 中等 相关标签 树   二叉搜索树   数学   动态规划   二叉树 给你一个整数  n  ,求恰由  n  个节点组成且节点值从  1  到  n  互不相同的  二叉搜索树  有多少种?返回满足题意的二叉搜索树的种数。 示例 1: 示例 2: 提示: 1 = n = 19 vectorint

    2024年02月06日
    浏览(35)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包