LeetCode: Palindrome Partitioning

LeetCode: 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
45
46
47
48
49
50
51
52
53
54
55

/**
* Created by hzhou on 2015/5/13.
* <p/>
* Given a string s, partition s such that every substring of the partition is a palindrome.
* <p/>
* Return all possible palindrome partitioning of s.
* <p/>
* For example, given s = "aab",
* Return
* <p/>
* <p/>
* [
* ["aa","b"],
* ["a","a","b"]
* ]
*/
public class PalindromePartitioning {
public List<List<String>> partition(String s) {
List<List<String>> result = new ArrayList<List<String>>();
if (s == null || s.isEmpty()) {
return result;
}
helper(s, new ArrayList<String>(), result, 0);
return result;
}
private void helper(String s, List<String> crt, List<List<String>> result, int start) {
if (start >= s.length()) {
result.add(new ArrayList<String>(crt));
}
for (int i = start + 1; i <= s.length(); i++) {
String sub = s.substring(start, i);
if (isPalindrome(sub)) {
List<String> tmp = new ArrayList<String>(crt);
tmp.add(sub);
helper(s, tmp, result, i);
}
}
}
private boolean isPalindrome(String s) {
if (s == null || s.length() <= 1) {
return true;
}
for (int i = 0; i < s.length() / 2; i++) {
if (s.charAt(i) != s.charAt(s.length() - 1 - i)) {
return false;
}
}
return true;
}
@Test
public void test() {
List<List<String>> result = partition("aab");
}
}