LeetCode - Palindrome Partitioning
Problem description
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
Example:
1
2
3
4
5
6
Input: "aab"
Output:
[
["aa","b"],
["a","a","b"]
]
Analysis
The first idea is to use divide and conquer, we split the String into left part and right part. And then the result should be the combination of left part and right part. But here’s a problem. Suppose we have a String “aab”, and we can split it in two different ways, “a” “ab” and “aa” “b”. And this make we get two duplicates combination of “a” “a” “b”.
The solution to address this problem is to use backtrack but not simply divide and conquer it.
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution {
public List<List<String>> partition(String s) {
List<List<String>> res = new ArrayList<>();
if (s.length() == 1){
List<String> list = new ArrayList<>();
list.add(s);
res.add(list);
return res;
}
if (map.getOrDefault(s, false) || isPalindrome(s)){
List<String> list = new ArrayList<>();
list.add(s);
res.add(list);
map.put(s, true);
}
else{
map.put(s, false);
}
for (int i = 1; i < s.length() ;i++){
String left = s.substring(0, i);
if (map.getOrDefault(left, false) || isPalindrome(left)){
map.put(left, true);
List<List<String>> right = partition(s.substring(i));
for (List<String> rightItem:right){
List<String> list = new ArrayList<>();
list.add(left);
list.addAll(rightItem);
res.add(new ArrayList<>(list));
}
}
else{
map.put(left, false);
}
}
return res;
}
HashMap<String, Boolean> map = new HashMap<>();
boolean isPalindrome(String s){
int l = 0;
int h = s.length() - 1;
while (l < h){
if (s.charAt(l) != s.charAt(h)){
return false;
}
l++;
h--;
}
return true;
}
}
Another point we need to point out is that we can use dp to get if a substring is palindromic quickly.
1
2
3
4
5
6
7
8
9
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[i-1][j+1])){
dp[i][j] = true;
}
}
}
And a simplified backtrack version:
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
class Solution {
List<List<String>> output = new ArrayList<>();
public List<List<String>> partition(String s) {
backtrack(s, new ArrayList<>(), 0);
return output;
}
public void backtrack(String s, List<String> temp, int start) {
if(start == s.length()) // add when results make up entire string s
output.add(new ArrayList<>(temp));
else {
for(int i = start; i < s.length(); i++) {
if(isPalindrome(s, start, i)) {
temp.add(s.substring(start, i+1));
backtrack(s, temp, i+1);
temp.remove(temp.size()-1);
}
}
}
}
public boolean isPalindrome(String s, int left, int right) {
while(left < right) {
if(s.charAt(left) != s.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
}
What to improve
- use dp to get palindromic substring
- use backtrack to prevent duplicates. Divide and conquer is not the silver bullet.