友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
131. 分割回文串
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串。返回 s 所有可能的分割方案。
示例 1：
输入：s = "aab" 输出：[["a","a","b"],["aa","b"]]
示例 2：
输入：s = "a" 输出：[["a"]]
提示：
-
1 <= s.length <= 16 -
s仅由小写英文字母组成
思路分析
回溯
-
一刷
-
二刷
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
/**
* 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]
*
* @author D瓜哥 · https://www.diguage.com
* @since 2020-01-04 19:04
*/
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;
}
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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-04-21 21:17:12
*/
public List<List<String>> partition(String s) {
List<List<String>> result = new ArrayList<>(s.length());
List<String> path = new ArrayList<>(s.length());
Map<String, Boolean> validMap = new HashMap<>(s.length());
backtrack(s, 0, result, path, validMap);
return result;
}
private void backtrack(String s, int index, List<List<String>> result,
List<String> path, Map<String, Boolean> validMap) {
if (index >= s.length()) {
result.add(new ArrayList<>(path));
return;
}
for (int i = index + 1; i <= s.length(); i++) {
String sub = s.substring(index, i);
boolean isValid;
if (validMap.containsKey(sub)) {
isValid = validMap.get(sub);
} else {
isValid = isPalindrome(sub);
validMap.put(sub, isValid);
}
if (!isValid) {
continue;
}
path.add(sub);
backtrack(s, i, result, path, validMap);
path.removeLast();
}
}
private boolean isPalindrome(String s) {
int left = 0, right = s.length() - 1;
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}