Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
Given s = "aab", return:
[
["aa","b"],
["a","a","b"]
]1 public class Solution { 2 /** 3 * @param s: A string 4 * @return: A list of lists of string 5 */ 6 7 public ArrayList<ArrayList<String>> partition(String str) { 8 ArrayList<ArrayList<String>> listAll = new ArrayList<ArrayList<String>>(); 9 10 if (str== null || str.length() == 0) return listAll; 11 12 for (int i = 1; i <= str.length(); i++) { 13 String strPart1 = str.substring(0, i); 14 String strPart2 = str.substring(i); 15 16 if (isPalindrome(strPart1)) { 17 if (strPart1.equals(str)) { 18 ArrayList<String> list = new ArrayList<String>(); 19 list.add(str); 20 listAll.add(list); 21 } else { 22 ArrayList<ArrayList<String>> temp = partition(strPart2); 23 for (int j = 0; j < temp.size(); j++) { 24 temp.get(j).add(0, strPart1); 25 listAll.add(new ArrayList<String>(temp.get(j))); 26 } 27 } 28 } 29 } 30 return listAll; 31 } 32 33 public boolean isPalindrome(String str) { 34 if (str == null || str.length() == 1) 35 return true; 36 37 int i = 0; 38 int j = str.length() - 1; 39 while (i < j) { 40 if (str.charAt(i) != str.charAt(j)) { 41 return false; 42 } 43 i++; 44 j--; 45 } 46 return true; 47 } 48 }
Given a string s, cut s into some substrings such that every substring is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
Given s = "aab",
Return 1 since the palindrome partitioning ["aa", "b"] could be produced using 1 cut.
分析：
用cuts[i]表示从0 到 i最小的cuts数。那么为了得到cuts[i], 我们需要从0到i，看string 的k (0 <= k < i) 到 i部分是否是palindrome。是的话，我们需要更新当前cuts[i]的值，因为我们有可能在这个时候找到一个更小的值。
1 public class Solution { 2 /** 3 * @param s a string 4 * @return an integer 5 */ 6 7 public int minCut(String s) { 8 if (s == null || s.length() <= 1) return 0; 9 10 int[] cuts = new int[s.length() + 1]; 11 for (int i = 1; i < cuts.length; i++) { 12 cuts[i] = i; 13 } 14 cuts[0] = 0; 15 16 for (int i = 1; i < cuts.length; i++) { 17 for (int j = 1; j <= i; j++) { 18 if (isPalindrome(s, j - 1, i - 1)) { 19 cuts[i] = Math.min(cuts[i], cuts[j - 1] + 1); 20 } 21 } 22 } 23 return cuts[s.length()]; 24 } 25 26 public boolean isPalindrome(String str, int start, int end) { 27 while(start < end) { 28 if (str.charAt(start) != str.charAt(end)) { 29 return false; 30 } 31 start++; 32 end--; 33 } 34 return true; 35 } 36 }
Palindrome Partitioning I & II
原文：http://www.cnblogs.com/beiyeqingteng/p/5655199.html