LeetCode 131.Palindrome Partitioning (分割回文串)

偏执的太偏执、 2022-05-08 09:28 196阅读 0赞

题目描述：

给定一个字符串 *s*，将 *s* 分割成一些子串，使每个子串都是回文串。

返回 *s* 所有可能的分割方案。

**示例:**

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

AC C++ Solution:

解题思路：  
循环遍历字符串，检查substr（0，i）是否是回文。如果是，则在子字符串的其余部分递归调用dfs（）：substr（i + 1，length）。到目前为止，将当前的回文分区保留在dfs（）的'path'参数中。到达字符串末尾时，在结果中添加当前分区。

代码：

class Solution {
    public:
        vector<vector<string>> partition(string s) {
            vector<vector<string> > ret;
            if(s.empty()) return ret;
            
            vector<string> path;
            dfs(0, s, path, ret);
            
            return ret;
        }
        
        void dfs(int index, string& s, vector<string>& path, vector<vector<string> >& ret) {
            if(index == s.size()) {
                ret.push_back(path);
                return;
            }
            for(int i = index; i < s.size(); ++i) {
                if(isPalindrome(s, index, i)) {
                    path.push_back(s.substr(index, i - index + 1));
                    dfs(i+1, s, path, ret);
                    path.pop_back();
                }
            }
        }
        
        bool isPalindrome(const string& s, int start, int end) {
            while(start <= end) {
                if(s[start++] != s[end--])
                    return false;
            }
            return true;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，196人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode-131. 分割回文串

目录题目思路回溯题目来源 [131. 分割回文串][131.] 题目思路切割问题类似组合问题。例如对于字符串abcd

深碍√TFBOYSˉ_/ 2024年03月26日 12:52/ 0 赞/ 54 阅读

相关 leetcode 131. 分割回文串

递归暴力求解将字符串进行分割，如果左边是回文串，则对右边进行分割，递归的出口是这个串被分割到空串 class Solution { public:

系统管理员/ 2023年10月10日 10:03/ 0 赞/ 40 阅读

相关 LeetCode131. 分割回文串

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。示例: 输入: “aab” 输出: [ ["

小咪咪/ 2022年11月06日 01:56/ 0 赞/ 125 阅读

相关 LeetCode 131. 分割回文串

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。示例: 输入: "aab" 输出:

刺骨的言语ヽ痛彻心扉/ 2022年11月06日 01:51/ 0 赞/ 223 阅读

相关 LeetCode 131. 分割回文串

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

冷不防/ 2022年11月04日 13:30/ 0 赞/ 164 阅读

相关 leetcode 131 分割回文串

前言题目：[131. 分割回文串][131.] 参考题解：[分割回文串-代码随想录][-] 提交代码先切割再判断方法一：思考了下，这道题目的思路为，

梦里梦外;/ 2022年09月12日 13:51/ 0 赞/ 174 阅读

相关 leetcode 131. Palindrome Partitioning | 131. 分割回文串（递归解法）

题目 [https://leetcode.com/problems/palindrome-partitioning/][https_leetcode.com_proble

客官°小女子只卖身不卖艺/ 2022年08月30日 15:51/ 0 赞/ 141 阅读

相关 [Leetcode][python]Palindrome Partitioning/Palindrome Partitioning II/分割回文串/分割回文串II

Palindrome Partitioning 题目大意将一个字符串分割成若干个子字符串，使得子字符串都是回文字符串，要求列出所有的分割方案。解题思路

清疚/ 2022年06月05日 03:11/ 0 赞/ 174 阅读

相关 LeetCode 132.Palindrome Partitioning II (分割回文串 II)

题目描述：给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。返回符合要求的最少分割次数。示例: 输入: "aab" 输出: 1

清疚/ 2022年05月08日 10:04/ 0 赞/ 183 阅读

相关 LeetCode 131.Palindrome Partitioning (分割回文串)

题目描述：给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。示例: 输入: "aab" 输出:

偏执的太偏执、/ 2022年05月08日 09:28/ 0 赞/ 197 阅读