0131._Palindrome_Partitioning.md

131. Palindrome Paritionaing

难度: Middle

刷题内容

原题连接

• https://leetcode-cn.com/problems/palindrome-partitioning/

内容描述

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

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

示例:

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

解题方案

思路 1

回溯，判断是否回文。

bool isValid(string str){
    for(int i=0;i<str.length()/2;i++){
        if(str[i]!=str[str.length()-i-1])
            return false;
    }
    return true;
}
void dfs(int start, vector<string>& path, vector<vector<string>>& ans, string s){
    if(start == s.length()){
        ans.push_back(path);
        return ;
    }
    for(int i=start;i<s.length();i++){
        if(isValid(s.substr(start, i-start+1))){
            path.push_back(s.substr(start, i-start+1));
            dfs(i+1, path, ans, s);
            path.pop_back();
        }
    }
    
}
vector<vector<string>> partition(string s) {
    vector<vector<string>> ans;
    if(s.length()==0)
        return ans;
    vector<string> path;
    dfs(0, path, ans, s);
    return ans;
}