Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
像这种求所有可能性的问题就不适合用DP做，比较适合dfs。
思路就是从头扫描，按顺序将palindrome放入结果中。
需要注意的是，这里判断是否为palindrome的方法是，将string反转，然后比较和原来的是否相同。
1 public static ArrayList<ArrayList<String>> partition(String s) { 2 ArrayList<String> tmp = new ArrayList<String>(); 3 ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>(); 4 partition(s, 0, tmp, result); 5 return result; 6 } 7 public static void partition(String s, int position, ArrayList<String> tmp, ArrayList<ArrayList<String>> result) { 8 if (position == s.length()) { 9 result.add(new ArrayList<String>(tmp)); 10 return; 11 } 12 else { 13 for (int i=position; i<s.length(); i++) { 14 String w = s.substring(position, i+1); 15 if (isPalindrome(w)) { 16 tmp.add(w); 17 partition(s, i+1, tmp, result); 18 tmp.remove(tmp.size()-1); 19 } 20 } 21 } 22 } 23 public static boolean isPalindrome(String a) { 24 StringBuilder x = new StringBuilder(a).reverse(); 25 return x.toString().equals(a); 26 }