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 =
Return
"aab"
,Return
[ ["aa","b"], ["a","a","b"] ]
For example: s = "aab"
start = 0
check substring(0, 1) -> (1, 2) -> (2, 3) -> add
remove (2, 3)
(0, 1) -> (1, 3) not palindrome
(0, 2) -> (2, 3) -> add
public class PalindromePartition { public ArrayList> partition(String s) { if (s == null) throw new NullPointerException("Null string!"); ArrayList > rst = new ArrayList > (); if (s.length() == 0) return rst; partitionString(s, rst, new ArrayList (), 0); return rst; } private void partitionString (String s, ArrayList > rst, ArrayList partition, int start) { if (start == s.length()) { rst.add(new ArrayList (partition)); return; } for (int i = start + 1; i <= s.length(); i++) { String tmp = s.substring(start, i); if (!isPalindrome(tmp)) continue; partition.add(tmp); partitionString(s, rst, partition, i); partition.remove(partition.size() - 1); } } private boolean isPalindrome(String s) { int start = 0; int end = s.length() - 1; while (start < end) { if (s.charAt(start) != s.charAt(end)) return false; start++; end--; } return true; } }
Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
For example, given s =
Return
"aab"
,Return
1
since the palindrome partitioning ["aa","b"]
could be produced using 1 cut.This problem is obviously a typical DP (when it comes to find the maximum or minimum, you probably want to start your approach of DP first).
I like to show things using examples, mainly because I am not at describing things.
s = "abbab"
s.charAt(i) 0 1 2 3 4
s a b b a b
possible places to cut: 0 1 2 3 4 5
So I define an array cut[s.length() + 1]. cut[i] is aimed to store the minimum cut needed for s.substring(0, i).
cut[0] = 0, obviously, empty string.
cut[1] = 0, because s.substring(0,1) is a palindrome (single character).
start from cut[2]:
1. if s.substring(0, i) is a palindrome, cut[i] = 0;
2. otherwise, if s.substring(start,i) (start = 1, ... i - 1) is a palindrome, cut[i] = cut[start] + 1;
return cut[s.length], which is cut[5] in this case.
The next part is, how to check if s.substring(start, end) is a palindrome. Of course we can do it iteratively, but is it more convenient if we draw a table of all palindrome substrings of s and just check the table every time?
Yep, that's pretty much the solution.
1. palindrome[i][i] is obviously a palindrome since it only contains one character.
2. palindrome[i][i + 1] is a palindrome if s.charAt(i) == s.charAt(j)
3. palindrome[i][j] is a palindrome if palindrome[i+1][j-1] && s.charAt(i) ==s.charAt(j)
start \ end 0 1 2 3 4
0 T F F T F
1 T T T F
2 T F T
3 T F
4 T
public class PalindromePartition { public int minCut(String s) { if (s == null || s.length() == 0) return 0; //************************************** // I write this single loop to check if the string itself is a plindrome, //alternatively you can include it into the matrix or write a boolean checkPalindrome (s) method int startp = 0; int endp = s.length() - 1; while (startp < endp) { if(s.charAt(startp) != s.charAt(endp)) break; startp++; endp--; } if (endp <= startp) return 0; //**************************************** int[] cut = new int[s.length() + 1]; boolean[][] palindromeMatrix = isPalindrome(s); cut[0] = 0; cut[1] = 0; for (int end = 2; end < cut.length; end++) { cut[end] = Integer.MAX_VALUE; if (palindromeMatrix[0][end - 1]) { cut[end] = 0; continue; } for (int start = 1; start < end; start++) { if (!palindromeMatrix[start][end - 1]) continue; cut[end] = Math.min(cut[end], cut[start] + 1); } } return cut[s.length()]; } private boolean[][] isPalindrome(String s) { boolean[][] palindromeMatrix = new boolean[s.length()][s.length()]; for (int i = 0; i < s.length(); i++) palindromeMatrix[i][i] = true; for (int i = 0; i < s.length() - 1; i++) palindromeMatrix[i][i + 1] = (s.charAt(i) == s.charAt(i + 1)); for (int length = 3; length < s.length(); length++) { for (int start = 0; start <= s.length() - length; start++) palindromeMatrix[start][start + length - 1] = (palindromeMatrix[start + 1][start + length - 2] && (s.charAt(start) == s.charAt(start + length - 1))); } return palindromeMatrix; } }
No comments:
Post a Comment