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"] ]
【解题思路】
DFS 找到s的所有的substring, 判断是否是palindrome, 如果是添加到result中去
public class Solution { public ArrayList<ArrayList<String>> partition(String s) { // Start typing your Java solution below // DO NOT write main() function ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>(); ArrayList<String> output = new ArrayList<String>(); int depth = 0, len = s.length(); palinPartition(s, 0, len, output, result); return result; } public void palinPartition(String s, int start, int len, ArrayList<String> output, ArrayList<ArrayList<String>> result){ if(start == len){ ArrayList<String> tmp = new ArrayList<String>(); tmp.addAll(output); result.add(tmp); return; } for(int i = start; i < len; i++){ if(isPalindrome(s, start, i)){ output.add(s.substring(start, i + 1)); palinPartition(s, i + 1, len, output, result); output.remove(output.size() - 1); } } } public boolean isPalindrome(String s, int start, int end){ while(start < end){ if(s.charAt(start) != s.charAt(end)){ return false; } start ++; end --; } return true; } }