leetcode 131. 分割回文串
题目：131. 分割回文串
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。
说明:
示例:
输入: “aab”
输出:
[
[“aa”,”b”],
[“a”,”a”,”b”]
]
方法：Backtracking（回溯）
思路：Backtracking（回溯），通过递归回溯前判断当前截取字符串是否是回文串对程序进行剪枝。
运行数据：执行用时：3 ms，内存消耗：40.4 MB
复杂度分析：
- 时间复杂度：O(n * 2^n)，n为9，最坏情况分割字符的时间复杂度为O(2^n)，判断回文串的时间复杂度为O(n)。
- 空间复杂度：O(n)，n为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
|
public List<List<String>> partition(String s) {
List<List<String>> result = new ArrayList<List<String>>();
backtracking(s, result, new ArrayList<>());
return result;
}
private void backtracking(String s, List<List<String>> result, List<String> tempList) {
if (s.length() == 0) {
result.add(new ArrayList<>(tempList));
return ;
}
for (int i = 0; i < s.length(); i++) {
if (isPalindromeString(s, 0, i)) {
tempList.add(s.substring(0, i + 1));
backtracking(s.substring(i + 1), result, tempList);
tempList.remove(tempList.size() - 1);
}
}
}
private boolean isPalindromeString(String str, int start, int end) {
while (start < end) {
if (str.charAt(start++) != str.charAt(end--)) {
return false;
}
}
return true;
}
|
学习所得，资料、图片部分来源于网络，如有侵权，请联系本人删除。
才疏学浅，若有错误或不当之处，可批评指正，还请见谅！
