【Leetcode】131. Palindrome Partitioning（回文字符串分区）

我会带着你远行 2022-04-24 15:22 154阅读 0赞

Given a string *s*, partition *s* such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of *s*.

**Example:**

Input: "aab"
    Output:
    [
      ["aa","b"],
      ["a","a","b"]
    ]

题目大意：

对给出的字符串，找出回文字符串的所有组合的方式。

解题思路：

DFS即可，每次开始位置为上一个回文字符串的结束位置。

class Solution {
    public:
        vector<vector<string>> partition(string s) {
            vector<vector<string>> ans;
            vector<string> tmp;
            helper(s, 0, ans, tmp);
            return ans;
        }
        
        void helper(string s, int begin, vector<vector<string> >& ans, vector<string >& tmp){
            if(begin==s.size()){
                ans.push_back(tmp);
                return;
            }
            
            for(int i=begin; i < s.size();i++){
                string cor_s = s.substr(begin, i-begin+1);
                if(valid(cor_s)){
                    // cout << cor_s << endl;
                    tmp.push_back(cor_s);
                    helper(s, i+1, ans, tmp);
                    tmp.pop_back();
                }
            }
            
        }
        
        bool valid(string s){
            for(int i =0;i<int(s.size()/2);i++){
                if(s[i]!=s[s.size()-1-i]) return false;
            }
            return true;
        }
        
    };

发表评论取消回复

表情：

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

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

相关阅读

相关 LeetCode - Medium - 131. Palindrome Partitioning

Topic Dynamic Programming Backtracking Depth-first Search Description [h

刺骨的言语ヽ痛彻心扉/ 2022年11月14日 10:08/ 0 赞/ 34 阅读

相关 leetcode131—Palindrome Partitioning

leetcode131—Palindrome Partitioning 1.原题 [原题链接][Link 1] > Given a string s, parti

ゝ一世哀愁。/ 2022年09月24日 10:28/ 0 赞/ 132 阅读

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

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

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

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

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

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

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

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

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

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

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

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

相关【Leetcode】131. Palindrome Partitioning（回文字符串分区）

Given a string s, partition s such that every substring of the partition is a palindrome

我会带着你远行/ 2022年04月24日 15:22/ 0 赞/ 155 阅读

相关 131. Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palind

亦凉/ 2022年02月15日 12:35/ 0 赞/ 190 阅读

相关【Leetcode】680. Valid Palindrome II（回文字符串）

Given a non-empty string `s`, you may delete at most one character. Judge whether you ca

喜欢ヅ旅行/ 2021年12月02日 00:18/ 0 赞/ 224 阅读

相关 [LeetCode] 131. Palindrome Partitioning_Medium tag: DFS, backtracking, Palindrome

Given a string s, partition s such that every substring of the partition is a palindrome

清疚/ 2021年11月16日 07:20/ 0 赞/ 194 阅读