Palindrome Partitioning
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
1234 [["aa","b"],["a","a","b"]]Palindrome Partitioning II
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 =
"aab"
,
Return1
since the palindrome partitioning["aa","b"]
could be produced using 1 cut.
Analysis
In these two problem, we often needs to check if the substring(i, j) of the original string is palindrome or not. So we need to save this very important information to an array to prevent checking a same substring for several times. This is a 2-D boolean array which is quite easy to generate. We can generate it from short length to long length. When s.charAt(i) is equal to s.charAt(j), if the array isPalindrome[i + 1][j – 1] is true, then we can update isPalindrome[i][j] = true.
In the first problem, we can use recursive function to generate all possible string lists.
In the second problem, if we use recursive solution, we will got TLE. So a DP solution is needed. We can use a 1-D array D[n] to save the minimum cut. For example, D[i] saves the number of minimum cut of substring(i, n). We can start from i = n – 1, and move i from right to left. When we want to get the D[i] for a new i, we can check every possible substrings from i to n, which means we can use another point j, in which j is between i and n. If substring(i, j) is a palindrome, then we can update D[i] = min(D[i], 1 + D[j + 1]).
This method can also be used in the first problem to save more time.
Code
Palindrome Partitioning (Recursive solution)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
public class Solution { List<List<String>> ret; public List<List<String>> partition(String s) { int n = s.length(); boolean[][] isPalindrome = new boolean[n][n]; for (int i = 0; i < n; i++) isPalindrome[i][i] = true; for (int i = n - 1; i >= 0; i--) { for (int j = i + 1; j < n; j++) { if (s.charAt(i) == s.charAt(j)) { if (j - i < 2 || isPalindrome[i + 1][j - 1]) isPalindrome[i][j] = true; } } } ret = new LinkedList<>(); List<String> list = new LinkedList<>(); partition(s, 0, isPalindrome, list); return ret; } private void partition(String s, int start, boolean[][] isPalindrome, List<String> list) { if (start == s.length()) { List<String> newList = new LinkedList<>(); newList.addAll(list); ret.add(newList); return; } for (int i = start; i < s.length(); i++) { if (isPalindrome[start][i]) { list.add(s.substring(start, i + 1)); partition(s, i + 1, isPalindrome, list); list.remove(list.size() - 1); } } } } |
Palindrome Partitioning (DP solution)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
import java.lang.reflect.Array; public class Solution { public List<List<String>> partition(String s) { int n = s.length(); boolean[][] isPalindrome = new boolean[n][n]; for (int i = 0; i < n; i++) isPalindrome[i][i] = true; for (int i = n - 1; i >= 0; i--) { for (int j = i + 1; j < n; j++) { if (s.charAt(i) == s.charAt(j)) { if (j - i < 2 || isPalindrome[i + 1][j - 1]) isPalindrome[i][j] = true; } } } List<List<String>>[] palindromes = (List<List<String>>[])Array.newInstance(List.class, n + 1); palindromes[n] = (List)(new LinkedList<List<String>>()); List<String> emptyList = new LinkedList<>(); palindromes[n].add(emptyList); for (int i = n - 1; i >= 0; i--) { palindromes[i] = (List)(new LinkedList<List<String>>()); for (int j = i; j < n; j++) { if (isPalindrome[i][j]) { List<List<String>> lists = palindromes[j + 1]; String substring = s.substring(i, j + 1); for (List<String> list : lists) { List<String> newList = new LinkedList<>(); newList.add(substring); newList.addAll(list); palindromes[i].add(newList); } } } } return palindromes[0]; } } |
The creation of generic array: http://www.quora.com/Java-programming-language/Why-does-Java-prohibit-generic-array-creation.
Palindrome Partitioning II
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
public class Solution { public int minCut(String s) { int n = s.length(); boolean[][] isPalindrome = new boolean[n][n]; for (int i = 0; i < n; i++) isPalindrome[i][i] = true; for (int i = n - 1; i >= 0; i--) { for (int j = i + 1; j < n; j++) { if (s.charAt(i) == s.charAt(j)) { if (j - i < 2 || isPalindrome[i + 1][j - 1]) isPalindrome[i][j] = true; } } } int[] minCut = new int[n + 1]; for (int i = n; i >= 0; i--) minCut[i] = n - 1 - i; for (int i = n - 1; i >= 0; i--) { for (int j = i; j < n; j++) { if (isPalindrome[i][j]) { minCut[i] = Math.min(minCut[i], 1 + minCut[j + 1]); } } } return minCut[0]; } } |
Complexity
In the first problem, assuming the total number of strings is k, then the complexity is $O(n^2 + k)$.
The complexity of second problem is $O(n^2)$.