I am solving the question of palindrome partitioning on Leetcode.
I have written a recursive solution which prints the correct Lists of substrings but for one of the test cases, the order in the list does not match the expected output.
Input:
cbbbcc
Output:
[["c","b","b","b","c","c"],["b","b","b","c","cc"],["b","c","bb","c","c"],["b","bb","c","cc"],["c","bb","b","c","c"],["bb","b","c","cc"],["c","bbb","c","c"],["bbb","c","cc"],["cbbbc","c"]]
Expected:
[["c","b","b","b","c","c"],["c","b","b","b","cc"],["c","b","bb","c","c"],["c","b","bb","cc"],["c","bb","b","c","c"],["c","bb","b","cc"],["c","bbb","c","c"],["c","bbb","cc"],["cbbbc","c"]]
I am not able to figure out why is my recursive call shifting the first element "c" in this example.
public class Solution {
public List<List<String>> partition(String s) {
List<List<String>> result = new ArrayList<>();
backTrack(result, new ArrayList<String>(), s);
return result;
}
private void backTrack(List<List<String>> result, List<String> cur, String s){
if(s.length() == 0)
result.add(new ArrayList<>(cur));
/* length = i+1 */
for(int i = 0; i < s.length(); i++){
if(isPalindrome(s.substring(0, i+1))){
cur.add(s.substring(0, i+1));
backTrack(result, cur, s.substring(i+1, s.length()));
cur.remove(s.substring(0, i+1));
}
}
}
private boolean isPalindrome(String s){
int start = 0, end = s.length() - 1;
char[] schars = s.toCharArray();
while(start < end){
if(schars[start] != schars[end])
return false;
start++;
end--;
}
return true;
}
}
I did go through an example and as per my logic, I do not see any reason that "c" should be displaced as in the output.
The problem is because of the way you expect add and remove to behave with your List.
Initially, you are building up cur from s (here cbbbcc):
s cur
1. cbbbcc []
2. bbbcc [c]
3. bbcc [c, b]
4. bcc [c, b, b]
5. cc [c, b, b, b]
6. c [c, b, b, b, c]
7. [c, b, b, b, c, c]
Now, the calls to backTrack() return in the reverse order 7, 6, 5, ...
Thus, this line:
cur.remove(s.substring(0, i+1));
is first run with the substring "c".
Ideally, your code should remove the rightmost "c" from cur. But the remove method removes the first "c" that it encounters, which is at position 0. From here on, your ordering is always wrong.
The easiest solution would be to always add to the first position to match the default behaviour for remove(). You would need to invert the String before using it in this way, though.
I've modified your code appropriately, here:
import java.util.*;
import java.lang.*;
public class Solution {
public List<List<String>> partition(String s) {
List<List<String>> result = new ArrayList<>();
backTrack(result, new ArrayList<String>(), new StringBuilder(s).reverse().toString()); // EDIT 1: Invert String
return result;
}
private void backTrack(List<List<String>> result, List<String> cur, String s) {
if(s.length() == 0) result.add(new ArrayList<>(cur));
for(int i = 0; i < s.length(); i++){
if(isPalindrome(s.substring(0, i+1))){
cur.add(0, s.substring(0, i+1)); // EDIT 2: Add to beginning of list
backTrack(result, cur, s.substring(i+1, s.length()));
cur.remove(s.substring(0, i+1));
}
}
}
private boolean isPalindrome(String s) {
int start = 0, end = s.length() - 1;
char[] schars = s.toCharArray();
while(start < end){
if(schars[start] != schars[end])
return false;
start++;
end--;
}
return true;
}
}
You can run in online here or below.
<script src="//repl.it/embed/JNx4/0.js"></script>Alternatively, instead of reversing the string and adding to the left of the list, you could simply remove() by finding the rightmost occurrence of the character in the list.