Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = "aab",
Return
[ ["aa","b"], ["a","a","b"] ]
public class Solution { ArrayList<ArrayList<String>> all=new ArrayList<ArrayList<String>>(); boolean isPalin(String s, int i, int j){ while(i<j){ if(s.charAt(i)!=s.charAt(j)) return false; i++; j--; } return true; } void dfs(String s, int start, ArrayList<String> al){ if(start==s.length()){ all.add(new ArrayList<String>(al)); return; } for(int i=start+1;i<=s.length();i++){ if(isPalin(s,start,i-1)){ al.add(s.substring(start,i)); //Start index is inclusive End index is exclusive
dfs(s,i,al); al.remove(al.size()-1);//i.e. 112 list:(1) list:(11) then do list(13)so,remove the second one } } } public ArrayList<ArrayList<String>> partition(String s) { all.clear(); ArrayList<String> al=new ArrayList<String>(); dfs(s,0,al); return all; } }
public class Solution { public ArrayList<ArrayList<String>> partition(String s) { ArrayList<ArrayList<String>> res = new ArrayList<ArrayList<String>>(); ArrayList<String> tmp = new ArrayList<String>(); dfs(res,tmp,s); return res; } public void dfs(ArrayList<ArrayList<String>> res, ArrayList<String> tmp, String s){ if (s.length()==0) res.add(new ArrayList<String>(tmp)); for(int i=1;i<=s.length();i++){ String substr = s.substring(0,i); if(isPalindrome(substr)){ ArrayList<String> list = new ArrayList<String>(tmp); list.add(substr); dfs(res,list,s.substring(i)); } } } public boolean isPalindrome(String s){ int i = 0; int j = s.length()-1; while(i<j){ if (s.charAt(i++) != s.charAt(j--)) return false; } return true; } }