题目
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1：
输入：s = "aab" 输出：[["a","a","b"],["aa","b"]]
示例 2：
输入：s = "a" 输出：[["a"]]
解题
方法一：回溯
class Solution { public: vector<vector<string>> res; vector<string> path; void backtracing(string& s,int startIndex){ if(startIndex>=s.size()){ res.push_back(path); return; } for(int i=startIndex;i<s.size();i++){ if(isPalindrome(s,startIndex,i)){ string str=s.substr(startIndex,i-startIndex+1); path.push_back(str); } else continue;//此行注释掉会报错?? backtracing(s,i+1); path.pop_back(); } } bool isPalindrome(string& s,int start,int end){ for(int i=start,j=end;i<j;i++,j--){ if(s[i]!=s[j]) return false; } return true; } vector<vector<string>> partition(string s) { backtracing(s,0); return res; } };
或者换种写法
class Solution { public: vector<vector<string>> res; vector<string> path; bool isPalindrome(string s){ int left=0; int right=s.size()-1; while(left<right){ if(s[left]!=s[right]){ return false; } left++; right--; } return true; } void backtracing(string s,int startIndex){ if(startIndex>=s.size()){ res.push_back(path); return; } for(int i=startIndex;i<s.size();i++){ string str=s.substr(startIndex,i-startIndex+1); if(isPalindrome(str)){ path.push_back(str); backtracing(s,i+1); path.pop_back(); } } } vector<vector<string>> partition(string s) { backtracing(s,0); return res; } };
java
class Solution { List<List<String>> res=new LinkedList<>(); List<String> path=new LinkedList<>(); void dfs(String s,int startIndex){ if(startIndex==s.length()){ res.add(new LinkedList<>(path)); return; } for(int i=startIndex;i<s.length();i++){ if(isValid(s,startIndex,i)){ path.add(s.substring(startIndex,i+1)); dfs(s,i+1); path.remove(path.size()-1); } } } boolean isValid(String s,int l,int r){ if(l>r) return false; for(int i=l,j=r;i<=j;i++,j--){ if(s.charAt(i)!=s.charAt(j)) return false; } return true; } public List<List<String>> partition(String s) { dfs(s,0); return res; } }
