第五章 - 高频考题（中等）
1906. 查询差绝对值的最小值
0131. 分割回文串
题目地址(131. 分割回文串)
题目描述
1
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
2
3
返回 s 所有可能的分割方案。
4
5
示例:
6
7
输入: "aab"
8
输出:
9
[
10
["aa","b"],
11
["a","a","b"]
12
]
Copied!
前置知识
- 回溯法
公司
- 阿里
- 腾讯
- 百度
- 字节
思路
这是一道求解所有可能性的题目， 这时候可以考虑使用回溯法。 回溯法解题的模板我们已经在很多题目中用过了， 这里就不多说了。大家可以结合其他几道题目加深一下理解。
这种题目其实有一个通用的解法，就是回溯法。网上也有大神给出了这种回溯法解题的[通用写法](https://leetcode.com/problems/combination-sum/discuss/16502/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partitioning))，这里的所有的解法使用通用方法解答。 除了这道题目还有很多其他题目可以用这种通用解法，具体的题目见后方相关题目部分。
这里我画了一个图：
关键点解析
- 回溯法
代码
- 语言支持：JS，Python3, CPP
JS Code:
1
/*
2
* @lc app=leetcode id=131 lang=javascript
3
*
4
* [131] Palindrome Partitioning
5
*/
6
7
function isPalindrom(s) {
8
let left = 0;
9
let right = s.length - 1;
10
11
while (left < right && s[left] === s[right]) {
12
left++;
13
right--;
14
}
15
16
return left >= right;
17
}
18
function backtrack(s, list, tempList, start) {
19
const sliced = s.slice(start);
20
21
if (isPalindrom(sliced) && tempList.join("").length === s.length)
22
list.push([...tempList]);
23
24
for (let i = 0; i < sliced.length; i++) {
25
const sub = sliced.slice(0, i + 1);
26
if (isPalindrom(sub)) {
27
tempList.push(sub);
28
} else {
29
continue;
30
}
31
backtrack(s, list, tempList, start + i + 1);
32
tempList.pop();
33
}
34
}
35
/**
36
* @param {string} s
37
* @return {string[][]}
38
*/
39
var partition = function (s) {
40
// "aab"
41
// ["aa", "b"]
42
// ["a", "a", "b"]
43
const list = [];
44
backtrack(s, list, [], 0);
45
return list;
46
};
Copied!
Python Code:
1
class Solution:
2
def partition(self, s: str) -> List[List[str]]:
3
"""回溯法"""
4
5
res = []
6
7
def helper(s, tmp):
8
"""
9
如果是空字符串，说明已经处理完毕
10
否则逐个字符往前测试，判断是否是回文
11
如果是，则处理剩余字符串，并将已经得到的列表作为参数
12
"""
13
if not s:
14
res.append(tmp)
15
for i in range(1, len(s) + 1):
16
if s[:i] == s[:i][::-1]:
17
helper(s[i:], tmp + [s[:i]])
18
19
helper(s, [])
20
return res
Copied!
CPP Code:
1
class Solution {
2
private:
3
vector<vector<string>> ans;
4
vector<string> tmp;
5
bool isPalindrome(string &s, int first, int last) {
6
while (first < last && s[first] == s[last]) ++first, --last;
7
return first >= last;
8
}
9
void dfs(string &s, int start) {
10
if (start == s.size()) { ans.push_back(tmp); return; }
11
for (int i = start; i < s.size(); ++i) {
12
if (isPalindrome(s, start, i)) {
13
tmp.push_back(s.substr(start, i - start + 1));
14
dfs(s, i + 1);
15
tmp.pop_back();
16
}
17
}
18
}
19
public:
20
vector<vector<string>> partition(string s) {
21
dfs(s, 0);
22
return ans;
23
}
24
};
Copied!
相关题目
最近更新 1yr ago