[Link] https://leetcode.com/problems/palindrome-partitioning/
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
//optimized with dp(less substring function called)
class Solution {
public List<List<String>> partition(String s) {
List<List<String>> ans = new ArrayList<>();
boolean[][] notP = new boolean[s.length()][s.length()];
String[][] dp = new String[s.length()][s.length()];
dfs(ans, new ArrayList<String>(), s,-1, notP, dp);
return ans;
}
public void dfs(List<List<String>> ans, ArrayList<String> ll, String s,int k, boolean[][] notP, String[][] dp){
if(k == s.length() - 1){
ans.add(new ArrayList<String>(ll));
return;
}
for(int i= k+1 ; i < s.length(); i++){
if(notP[k+1][i]) continue;
else if(dp[k+1][i] != null) {
ll.add(dp[k+1][i]);
dfs(ans, ll, s, i, notP, dp);
ll.remove(ll.size() -1);
} else {
String str=s.substring(k+1,i+1);
if(isPal(s, k + 1, i, notP)){
ll.add(str);
dp[k+1][i] = str;
dfs(ans, ll,s,i, notP, dp);
ll.remove(ll.size() -1);
} else notP[k+1][i] = true;
}
}
}
public boolean isPal(String s, int start, int end, boolean[][] notP){
for(int l = start, r = end; l < r; l++, r--)
if(s.charAt(l) != s.charAt(r)) {
while(l >= start && r <= end && !notP[l][r]) {
notP[l--][r--] = true;
}
return false;
}
return true;
}
}
First attempt(Full dp + dfs) </br>
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
class Solution {
public List<List<String>> partition(String s) {
int len = s.length();
char[] ch = s.toCharArray();
boolean[][] pal = new boolean[len][len];
for(int i = 0; i < len - 1; i++) {
pal[i][i] = true;
if(ch[i] == ch[i+1]) pal[i][i+1] = true;
}
pal[len-1][len-1] = true;
for(int di = 2; di < len; di++)
for(int i = 0; i < len - di; i++)
if(ch[i] == ch[i+di] && pal[i+1][i+di-1]) pal[i][i+di] = true;
LinkedList<Integer> ll = new LinkedList<>();
List<List<String>> list = new LinkedList<>();
dfs(pal, ch, -1, ll, list, len);
return list;
}
void dfs(boolean[][] pal, char[] ch, int cur, LinkedList<Integer> ll, List<List<String>> list, int len) {
if(cur == len - 1) {
LinkedList<String> temp = new LinkedList<>();
int startIdx = 0;
for(int idx: ll) {
temp.add(String.copyValueOf(ch, startIdx, idx - startIdx + 1));
startIdx = idx + 1;
}
list.add(temp);
return;
}
for(int i = cur + 1; i < len; i++) {
if(pal[cur+1][i]) {
ll.add(i);
dfs(pal, ch, i, ll, list, len);
ll.removeLast();
}
}
}
<T> void print(T s) { System.out.print(s); }
}