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;
}
