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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| /*
* 131. Palindrome Partitioning
My Submissions QuestionEditorial Solution
Total Accepted: 66490 Total Submissions: 239524 Difficulty: Medium
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
[
["aa","b"],
["a","a","b"]
]
Hide Company Tags Bloomberg
Hide Tags Backtracking
Hide Similar Problems (H) Palindrome Partitioning II
*/
package dfs;
import java.util.*;
public class ParlindromePartition {
public static void main(String[] args) {
// TODO Auto-generated method stub
ParlindromePartition pt = new ParlindromePartition();
String s = "aab";
List<List<String>> res = pt.partition(s);
// System.out.print(res);
}
public List<List<String>> partition(String s) {
/*
* Time complexity is O(n*(2^n)). The function isPalindrome is O(n)
* https://leetcode.com/discuss/18984/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.
*/
List<List<String>> res = new ArrayList<List<String>>();
List<String> cur = new ArrayList<>();
backtrack(res, cur, 0, s);
System.out.print(res);
return res;
}
public void backtrack(List<List<String>> res, List<String> cur, int pos, String s) {
if (pos == s.length()) {
res.add(new ArrayList<String>(cur));
}
for (int i = pos; i < s.length(); i++) {
if (isPalindrome(s, pos, i)) {
cur.add(s.substring(pos, i + 1));
backtrack(res, new ArrayList<String>(cur), i + 1, s);
cur.remove(cur.size() - 1);
}
}
}
public boolean isPalindrome(String str, int l, int r) {
while (l < r) {
if (str.charAt(l++) != str.charAt(r--)) {
return false;
}
}
return true;
}
}
|