【LeetCode热题100】131. 分割回文串(回溯)

一.题目要求

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

二.题目难度

中等

三.输入样例

示例 1:
输入:s = “aab”
输出:[[“a”,“a”,“b”],[“aa”,“b”]]

示例 2:
输入:s = “a”
输出:[[“a”]]

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

四.解题思路

解法1:输入视角,每次切割或者不切割
在这里插入图片描述

解法2:答案视角,枚举所有可能子串
在这里插入图片描述

五.代码实现

解1

class Solution {
public:
    bool isHui(const string& str) {
        for (int i = 0, j = str.size() - 1; i < j; i++, j--) {
            if (str[i] != str[j])
                return false;
        }
        return true;
    }

    vector<vector<string>> partition(string s) {
        vector<vector<string>> ans;
        vector<string> path;
        dfs(ans, path, s, 1);
        return ans;
    }
    /*
    cutIndex为当前待处理元素进行切割的位置
    从待处理串第一个字母末尾开始走,每次都选择是切割还是不切割
        如果切割,先判断切下来的子串是否是回文串,若是,进行递归
        如果不切割,令cutIndex后移一位
    直到待处理string为空且每次切下来的子串都是回文串 则加入答案
    */
    void dfs(vector<vector<string>>& ans, vector<string>& path, string& s, int cutIndex) {
        if (s == "") {
            ans.push_back(path);
            return;
        }
        if (cutIndex > s.size()) {
            return;
        }
        // 在该位置做切割
        string str = s.substr(0, cutIndex);
        
        //如果是回文串就递归处理剩下的串
        if (isHui(str)) {
            string _s = s.substr(cutIndex);
            path.push_back(str);
            dfs(ans, path, _s, 1);
            path.pop_back();
        }
        // 在该位置不做切割
        dfs(ans, path, s, cutIndex + 1);
    }
};

解2

class Solution {
public:
    bool isHui(const string& str) {
        for (int i = 0, j = str.size() - 1; i < j; ++i, --j) {
            if (str[i] != str[j])
                return false;
        }
        return true;
    }

    vector<vector<string>> partition(string s) {
        vector<vector<string>> ans;
        vector<string> path;
        dfs(ans, path, s, 0); // 从字符串的开始位置开始深度优先搜索
        return ans;
    }

    void dfs(vector<vector<string>>& ans, vector<string>& path, const string& s,
             int start) {
        if (start ==
            s.size()) { // 如果已经遍历到字符串末尾,则将当前路径加入答案
            ans.push_back(path);
            return;
        }
        for (int i = start; i < s.size(); ++i) {
            string str = s.substr(start, i - start + 1);
            if (isHui(str)) { // 只有当当前字符串是回文时,才继续递归
                path.push_back(str);
                dfs(ans, path, s, i + 1); // 从下一个字符开始继续递归搜索
                path.pop_back();          // 回溯
            }
        }
    }
};

六.题目总结

相关推荐

  1. leetcodeHOT leetcode131. 分割

    2024-04-03 18:26:01       11 阅读
  2. LeetCode-100:131. 分割

    2024-04-03 18:26:01       7 阅读
  3. leetcode 131. 分割

    2024-04-03 18:26:01       22 阅读
  4. LeetCodeHot100 - 最长

    2024-04-03 18:26:01       5 阅读
  5. LeetCode---

    2024-04-03 18:26:01       6 阅读

最近更新

  1. leetcode705-Design HashSet

    2024-04-03 18:26:01       8 阅读
  2. Unity发布webgl之后打开streamingAssets中的html文件

    2024-04-03 18:26:01       8 阅读
  3. vue3、vue2中nextTick源码解析

    2024-04-03 18:26:01       8 阅读
  4. 高级IO——React服务器简单实现

    2024-04-03 18:26:01       8 阅读
  5. 将图片数据转换为张量(Go并发处理)

    2024-04-03 18:26:01       7 阅读
  6. go第三方库go.uber.org介绍

    2024-04-03 18:26:01       8 阅读
  7. 前后端AES对称加密 前端TS 后端Go

    2024-04-03 18:26:01       10 阅读

热门阅读

  1. 学习总结!

    2024-04-03 18:26:01       4 阅读
  2. Vue3中props和emits的使用总结

    2024-04-03 18:26:01       6 阅读
  3. IO和NIO的主要区别在哪里?

    2024-04-03 18:26:01       5 阅读
  4. CSS 滚动条样式修改

    2024-04-03 18:26:01       5 阅读
  5. codeforces round 936 div2(a,b,c)

    2024-04-03 18:26:01       6 阅读
  6. Python程序设计 魔法函数

    2024-04-03 18:26:01       5 阅读
  7. ACI Fabric

    2024-04-03 18:26:01       5 阅读
  8. wencoo个人的博客目录索引-更新

    2024-04-03 18:26:01       4 阅读
  9. Oracle extent、segment、datafile、tablespace及存储关系

    2024-04-03 18:26:01       4 阅读
  10. Oracle密码文件

    2024-04-03 18:26:01       4 阅读
  11. SpringMVC 中实现自定义转换

    2024-04-03 18:26:01       5 阅读
  12. 开源的分布式文件系统 Fastdfs 安装入门介绍

    2024-04-03 18:26:01       5 阅读
  13. 在stable diffusion中如何分辨lora、大模型、controlnet

    2024-04-03 18:26:01       5 阅读