/
_0131_PalindromePartitioning.java
74 lines (69 loc) · 2.3 KB
/
_0131_PalindromePartitioning.java
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
package com.diguage.algorithm.leetcode;
import java.util.*;
/**
* = 131. Palindrome Partitioning
*
* https://leetcode.com/problems/palindrome-partitioning/[Palindrome Partitioning - LeetCode]
*
* Given a string s, partition s such that every substring of the partition is a palindrome.
*
* Return all possible palindrome partitioning of s.
*
* .Example:
* [source]
* ----
* Input: "aab"
* Output:
* [
* ["aa","b"],
* ["a","a","b"]
* ]
* ----
*
* @author D瓜哥, https://www.diguage.com/
* @since 2020-01-04 19:04
*/
public class _0131_PalindromePartitioning {
/**
* Runtime: 2 ms, faster than 94.23% of Java online submissions for Palindrome Partitioning.
* Memory Usage: 39.2 MB, less than 95.45% of Java online submissions for Palindrome Partitioning.
*
* Copy from: https://leetcode.com/problems/palindrome-partitioning/discuss/41963/Java%3A-Backtracking-solution.[Java: Backtracking solution. - LeetCode Discuss]
*/
public List<List<String>> partition(String s) {
if (Objects.isNull(s) || s.length() == 0) {
return Collections.emptyList();
}
List<List<String>> result = new LinkedList<>();
List<String> current = new ArrayList<>();
dfs(s, 0, current, result);
return result;
}
private void dfs(String s, int index, List<String> current, List<List<String>> result) {
if (index == s.length()) {
result.add(new ArrayList<>(current));
} else {
for (int i = index; i < s.length(); i++) {
if (isPalindrome(s, index, i)) {
current.add(s.substring(index, i + 1));
dfs(s, i + 1, current, result);
current.remove(current.size() - 1);
}
}
}
}
private boolean isPalindrome(String s, int low, int high) {
while (low < high) {
if (!Objects.equals(s.charAt(low++), s.charAt(high--))) {
return false;
}
}
return true;
}
public static void main(String[] args) {
_0131_PalindromePartitioning solution = new _0131_PalindromePartitioning();
String s1 = "aab";
List<List<String>> r1 = solution.partition(s1);
System.out.println(Arrays.deepToString(r1.toArray()));
}
}