http://www.cnblogs.com/springfor/p/3884197.html
Related: LeetCode 132 - Palindrome Partitioning II
1 public ArrayList<ArrayList<String>> partition(String s) {
2 ArrayList<String> item = new ArrayList<String>();
3 ArrayList<ArrayList<String>> res = new ArrayList<ArrayList<String>>();
4
5 if(s==null||s.length()==0)
6 return res;
7
8 dfs(s,0,item,res);
9 return res;
10 }
12 public void dfs(String s, int start, ArrayList<String> item, ArrayList<ArrayList<String>> res){
13 if (start == s.length()){
14 res.add(new ArrayList<String>(item));
15 return;
16 }
17
18 for (int i = start; i < s.length(); i++) {
19 String str = s.substring(start, i+1);
20 if (isPalindrome(str)) {
21 item.add(str);
22 dfs(s, i+1, item, res);
23 item.remove(item.size() - 1);
24 }
25 }
26 }
27
28
29 public boolean isPalindrome(String s){
30 int low = 0;
31 int high = s.length()-1;
32 while(low < high){
33 if(s.charAt(low) != s.charAt(high))
34 return false;
35 low++;
36 high--;
37 }
38 return true;
39 }
https://leetcode.com/discuss/9623/my-java-dp-only-solution-without-recursion-o-n-2
Big-O gives an upper-bound. That is, if the algorithm's running time is O(n^2), it says that the algorithm takes at most (some constant times) n^2 steps on these inputs. However, in the worst case, we will need at least 2^n steps.
public static List<List<String>> partition(String s) {
int len = s.length();
List<List<String>>[] result = new List[len + 1];
result[0] = new ArrayList<List<String>>();
result[0].add(new ArrayList<String>());
boolean[][] pair = new boolean[len][len];
for (int i = 0; i < s.length(); i++) {
result[i + 1] = new ArrayList<List<String>>();
for (int left = 0; left <= i; left++) {
if (s.charAt(left) == s.charAt(i) && (i-left <= 1 || pair[left + 1][i - 1])) {
pair[left][i] = true;
String str = s.substring(left, i + 1);
for (List<String> r : result[left]) {
List<String> ri = new ArrayList<String>(r);
ri.add(str);
result[i + 1].add(ri);
}
}
}
}
return result[len];
}
https://leetcode.com/discuss/9735/classic-recursive-solution-in-java
https://leetcode.com/discuss/18984/java-backtracking-solution
X. Brute force
https://discuss.leetcode.com/topic/1524/shouldn-t-we-use-dp-in-addition-to-dfs
Related: LeetCode 132 - Palindrome Partitioning II
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"]
]
X. DP
Time: O(2^N)
// Space: O(N * 2^N)
https://discuss.leetcode.com/topic/2884/my-java-dp-only-solution-without-recursion-o-n-2
Here the pair is to mark a range for the substring is a Pal. if pair[i][j] is true, that means sub string from
i to j is pal.
public List<List<String>> partition(String s) {
List<List<String>> res = new ArrayList<>();
if (s == null || s.isEmpty()) return res;
List<String> first = new ArrayList<>();
first.add(s.charAt(0) + "");
res.add(first);
for (int i = 1; i < s.length(); i++) {
String ch = s.charAt(i) + "";
int count = res.size();
for (int j = 0; j < count; j++) {
List<String> l = res.get(j);
int last = l.size() - 1;
if (l.get(last).equals(ch)) {
List<String> l2 = new ArrayList<>(l);
l2.add(l2.remove(last) + ch);
res.add(l2);
}
if (last > 0 && l.get(last - 1).equals(ch)) {
List<String> l2 = new ArrayList<>(l);
l2.add(l2.remove(last - 1) + l2.remove(last - 1) + ch);
res.add(l2);
}
l.add(ch);
}
}
return res;
}
X. No need to store all previous layershttps://leetcode.com/problems/palindrome-partitioning/discuss/41974/My-Java-DP-only-solution-without-recursion.-O(n2)
public static List<List<String>> partition(String s) {
int len = s.length();
List<List<String>>[] result = new List[len + 1];
result[0] = new ArrayList<List<String>>();
result[0].add(new ArrayList<String>());
boolean[][] pair = new boolean[len][len];
for (int i = 0; i < s.length(); i++) {
result[i + 1] = new ArrayList<List<String>>();
for (int left = 0; left <= i; left++) {
if (s.charAt(left) == s.charAt(i) && (i-left <= 1 || pair[left + 1][i - 1])) {
pair[left][i] = true;
String str = s.substring(left, i + 1);
for (List<String> r : result[left]) {
List<String> ri = new ArrayList<String>(r);
ri.add(str);
result[i + 1].add(ri);
}
}
}
}
return result[len];
}
Here the pair is to mark a range for the substring is a Pal. if pair[i][j] is true, that means sub string from i to j is pal.
The result[i], is to store from beginng until current index i (Non inclusive), all possible partitions. From the past result we can determine current result
https://leetcode.com/discuss/26043/concise-java-solutionhttps://leetcode.com/discuss/4788/shouldnt-we-use-dp-in-addition-to-dfs
Since this function "isPalindrome" needs to be called once for every prefix, that would make the overall time complexity O(N * 2^N).So my questions is: why don't we first use DP to find out if each substring is palindromic, which takes O(N^2) time and space? This would be nothing compared to the O(2^N) possible partitions, but saves us the need to call the O(N) isPalindrome function, thus brings down the overall time complexity to O(2^N) from O(N * 2^N).
public List<List<String>> partition(String s) {
List<List<String>> res = new ArrayList<>();
boolean[][] dp = new boolean[s.length()][s.length()];
for(int i = 0; i < s.length(); i++) {
for(int j = 0; j <= i; j++) {
if(s.charAt(i) == s.charAt(j) && (i - j <= 2 || dp[j+1][i-1])) {
dp[j][i] = true;
}
}
}
helper(res, new ArrayList<>(), dp, s, 0);
return res;
}
private void helper(List<List<String>> res, List<String> path, boolean[][] dp, String s, int pos) {
if(pos == s.length()) {
res.add(new ArrayList<>(path));
return;
}
for(int i = pos; i < s.length(); i++) {
if(dp[pos][i]) {
path.add(s.substring(pos,i+1));
helper(res, path, dp, s, i+1);
path.remove(path.size()-1);
}
}
}
X. DFS + cache
The worst-case running time is O(n * 2^n). This is of course exponential as you suspected, but not as bad as O(n^n).
Here's how I got O(n * 2^n): Your top-level function has an O(n^2) loop to initialize memo, and then a call to helper on the entire string. So if we write H(n) for the cost of calling helper with (s.length()-start) equal to n, then the total cost of your algorithm will be
cost = H(n) + O(n^2)
The base case for H(n) is when s.length() - start equals 1, and then it's just the cost of copying the list:
H(1) = O(n)
And for the recursive case, if the if condition memo[start][end] is true every time, there will be (n-1) recursive calls on size (n-1), (n-2), (n-3), ..., 2, 1. In addition to these recursive calls to helper, you also have to call the substr function on the same sizes, which costs O(n^2) in total. So overall the cost of H(n), for n>1, is
H(n) = H(n-1) + H(n-2) + ... + H(1) + O(n^2)
(I would write that as a summation but SO doesn't have LaTeX support.)
Now you can write the same expression for H(n-1), then substitute back to simplify:
H(n) = 2 H(n-1) + O(n)
And this solves to
H(n) = O(n * 2^n)
Since that is larger than O(n^2), the whole cost is also O(n * 2^n).
Note: You could slightly improve this by pre-computing all the substrings up front, in a single O(n^3) loop. You might as well do the same for the memo array. However, this doesn't change the asymptotic big-O bound.
In fact, O(n * 2^n) is optimal, because in the worst case the string is a repetition of the same character n times, like "aaaaaa", in which case there are 2^n possible partitions, each having size n, for a total output size of Ω(n * 2^n).
How did you arrive at H(n) = 2*H(n-1) + O(n)? Is it that (a) H(n-1) = H(n-2) + H(n-3) + ... + H(1) + O((n-1)^2); (b) O(n^2) = O(n) + O((n-1)^2) and therefore H(n) = H(n-1) + [ H(n-2) + ... + H(1) + O((n-1)^2) ] + O(n) = 2*H(n-1) + O(n)? Is it correct? I am not sure whether (b) is legit or not.
You are correct there is something slightly "loose" in my reasoning concerning (b). The key is that the two big-O's that are being subtracted there are really the same function. To be more pedantic, we should define a function g(n) = the time to call substr on sizes (n-1), (n-2), ..., 1. Then we have H(n) = H(n-1) + ... + H(1) + g(n), which you can now simplify to H(n) = 2*H(n-1) + g(n) - g(n-1). Finally, you say that the difference g(n) - g(n-1) is the time to call substr on size (n-1), which is O(n) as needed
Should be O(n*2^n). You are basically trying out every possible partition out there. For a string with length n, you will have 2^(n - 1) ways to partition it. This is because, a partition is equivalent of putting a "|" in b/t two chars. There are n - 1 such slots to place a "|". There are only two choice for each slot - placing a "|" or not placing a "|". Thus 2^(n - 1) ways to place "|"s.
Then for each unique partitioning, you have to traverse the entire string (in the worst case when you have repeating chars) to make sure every partition is a palindrome. so n * 2 ^ (n - 1) = O(n*2^n).
https://discuss.leetcode.com/topic/37756/java-dp-dfs-solution
The normal dfs backtracking will need to check each substring for palindrome, but a dp array can be used to record the possible break for palindrome before we start recursion.
first, I ask myself that how to check if a string is palindrome or not, usually a two point solution scanning from front and back. Here if you want to get all the possible palindrome partition, first a nested for loop to get every possible partitions for a string, then a scanning for all the partitions. That's a O(n^2) for partition and O(n^2) for the scanning of string, totaling at O(n^4) just for the partition. However, if we use a 2d array to keep track of any string we have scanned so far, with an addition pair, we can determine whether it's palindrome or not by justing looking at that pair, which is this line if(s.charAt(i) == s.charAt(j) && (i - j <= 2 || dp[j+1][i-1])). This way, the 2d array dp contains the possible palindrome partition among all.
second, based on the prescanned palindrome partitions saved in dp array, a simple backtrack does the job.
public List<List<String>> partition(String s) {
List<List<String>> res = new ArrayList<>();
boolean[][] dp = new boolean[s.length()][s.length()];
for(int i = 0; i < s.length(); i++) {
for(int j = 0; j <= i; j++) {
if(s.charAt(i) == s.charAt(j) && (i - j <= 2 || dp[j+1][i-1])) {
dp[j][i] = true;
}
}
}
helper(res, new ArrayList<>(), dp, s, 0);
return res;
}
private void helper(List<List<String>> res, List<String> path, boolean[][] dp, String s, int pos) {
if(pos == s.length()) {
res.add(new ArrayList<>(path));
return;
}
for(int i = pos; i < s.length(); i++) {
if(dp[pos][i]) {
path.add(s.substring(pos,i+1));
helper(res, path, dp, s, i+1);
path.remove(path.size()-1);
}
}
}
https://www.jiuzhang.com/solutions/palindrome-partitioning/
X. DFS
https://discuss.leetcode.com/topic/6186/java-backtracking-solution
if the input is "aab", check if [0,0] "a" is palindrome. then check [0,1] "aa", then [0,2] "aab".
While checking [0,0], the rest of string is "ab", use ab as input to make a recursive call.
in this example, in the loop of i=l+1, a recursive call will be made with input = "ab".
Every time a recursive call is made, the position of l move right.
How to define a correct answer?
Think about DFS, if the current string to be checked (Palindrome) contains the last position, in this case "c", this path is a correct answer, otherwise, it's a false answer.
line 13: is the boundary to check if the current string contains the last element.
l>=s.length()
List<List<String>> resultLst;
ArrayList<String> currLst;
public List<List<String>> partition(String s) {
resultLst = new ArrayList<List<String>>();
currLst = new ArrayList<String>();
backTrack(s,0);
return resultLst;
}
public void backTrack(String s, int l){
if(currLst.size()>0 //the initial str could be palindrome
&& l>=s.length()){
List<String> r = (ArrayList<String>) currLst.clone();
resultLst.add(r);
}
for(int i=l;i<s.length();i++){
if(isPalindrome(s,l,i)){
if(l==i)
currLst.add(Character.toString(s.charAt(i)));
else
currLst.add(s.substring(l,i+1));
backTrack(s,i+1);
currLst.remove(currLst.size()-1);
}
}
}
public boolean isPalindrome(String str, int l, int r){
if(l==r) return true;
while(l<r){
if(str.charAt(l)!=str.charAt(r)) return false;
l++;r--;
}
return true;
}
这里想法是，用递归循环找子问题的方法，把母串按所有组合可能性拆分，如果是回文，就加进来，当层数为s的length时就有一个结果了。 这里需要判断是否为回文。 利用validPalindrome的思想很容易就写出来了（这里不需要判断大小写还有有没有别的字符）。
2 ArrayList<String> item = new ArrayList<String>();
3 ArrayList<ArrayList<String>> res = new ArrayList<ArrayList<String>>();
4
5 if(s==null||s.length()==0)
6 return res;
7
8 dfs(s,0,item,res);
9 return res;
10 }
12 public void dfs(String s, int start, ArrayList<String> item, ArrayList<ArrayList<String>> res){
13 if (start == s.length()){
14 res.add(new ArrayList<String>(item));
15 return;
16 }
17
18 for (int i = start; i < s.length(); i++) {
19 String str = s.substring(start, i+1);
20 if (isPalindrome(str)) {
21 item.add(str);
22 dfs(s, i+1, item, res);
23 item.remove(item.size() - 1);
24 }
25 }
26 }
27
28
29 public boolean isPalindrome(String s){
30 int low = 0;
31 int high = s.length()-1;
32 while(low < high){
33 if(s.charAt(low) != s.charAt(high))
34 return false;
35 low++;
36 high--;
37 }
38 return true;
39 }
https://leetcode.com/discuss/9623/my-java-dp-only-solution-without-recursion-o-n-2
Here the pair is to mark a range for the substring is a Pal. if pair[i][j] is true, that means sub string from i to j is pal.
The result[i], is to store from beginng until current index i (Non inclusive), all possible partitions. From the past result we can determine current result.
public static List<List<String>> partition(String s) {
int len = s.length();
List<List<String>>[] result = new List[len + 1];
result[0] = new ArrayList<List<String>>();
result[0].add(new ArrayList<String>());
boolean[][] pair = new boolean[len][len];
for (int i = 0; i < s.length(); i++) {
result[i + 1] = new ArrayList<List<String>>();
for (int left = 0; left <= i; left++) {
if (s.charAt(left) == s.charAt(i) && (i-left <= 1 || pair[left + 1][i - 1])) {
pair[left][i] = true;
String str = s.substring(left, i + 1);
for (List<String> r : result[left]) {
List<String> ri = new ArrayList<String>(r);
ri.add(str);
result[i + 1].add(ri);
}
}
}
}
return result[len];
}
https://leetcode.com/discuss/9735/classic-recursive-solution-in-java
https://leetcode.com/discuss/18984/java-backtracking-solution
X. Brute force
https://discuss.leetcode.com/topic/1524/shouldn-t-we-use-dp-in-addition-to-dfs
I understand this problem can be solved easily with DFS. The basic idea is that for each palindromic prefix, recursively obtain the palindrome partitioning of the remaining substring. As far as I am concerned, this is, to say the least, an O(2^N) algorithm in the worst case (e.g., for strings like "aaaaa") since there are 2^N partitions.
However, in most implementations I saw online, people use an O(N) function to compute if each prefix is a palindrome, as in the following code, which can be found Here
Since this function "isPalindrome" needs to be called once for every prefix, that would make the overall time complexity O(N * 2^N).
So my questions is: why don't we first use DP to find out if each substring is palindromic, which takes O(N^2) time and space? This would be nothing compared to the O(2^N) possible partitions, but saves us the need to call the O(N) isPalindrome function, thus brings down the overall time complexity to O(2^N) from O(N * 2^N).
public ArrayList<ArrayList<String>> partition(String s) { ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>(); if (s == null || s.length() == 0) { return result; } ArrayList<String> partition = new ArrayList<String>();//track each possible partition addPalindrome(s, 0, partition, result); return result; } private void addPalindrome(String s, int start, ArrayList<String> partition, ArrayList<ArrayList<String>> result) { //stop condition if (start == s.length()) { ArrayList<String> temp = new ArrayList<String>(partition); result.add(temp); return; } for (int i = start + 1; i <= s.length(); i++) { String str = s.substring(start, i); if (isPalindrome(str)) { partition.add(str); addPalindrome(s, i, partition, result); partition.remove(partition.size() - 1); } } } private boolean isPalindrome(String str) { int left = 0; int right = str.length() - 1; while (left < right) { if (str.charAt(left) != str.charAt(right)) { return false; } left++; right--; } return true; } |
