0131. 分割回文串
https://leetcode-cn.com/problems/palindrome-partitioning/
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例:
输入: "aab"
输出:
[
["aa","b"],
["a","a","b"]
]
- 回溯法
- 阿里
- 腾讯
- 百度
- 字节
这是一道求解所有可能性的题目， 这时候可以考虑使用回溯法。 回溯法解题的模板我们已经在很多题目中用过了， 这里就不多说了。大家可以结合其他几道题目加深一下理解。
这种题目其实有一个通用的解法，就是回溯法。网上也有大神给出了这种回溯法解题的通用写法，这里的所有的解法使用通用方法解答。 除了这道题目还有很多其他题目可以用这种通用解法，具体的题目见后方相关题目部分。
这里我画了一个图：
- 回溯法
- 语言支持：JS，Python3, CPP
JS Code:
/*
* @lc app=leetcode id=131 lang=javascript
*
* [131] Palindrome Partitioning
*/
function isPalindrom(s) {
let left = 0;
let right = s.length - 1;
while (left < right && s[left] === s[right]) {
left++;
right--;
}
return left >= right;
}
function backtrack(s, list, tempList, start) {
const sliced = s.slice(start);
if (isPalindrom(sliced) && tempList.join("").length === s.length)
list.push([...tempList]);
for (let i = 0; i < sliced.length; i++) {
const sub = sliced.slice(0, i + 1);
if (isPalindrom(sub)) {
tempList.push(sub);
} else {
continue;
}
backtrack(s, list, tempList, start + i + 1);
tempList.pop();
}
}
/**
* @param {string} s
* @return {string[][]}
*/
var partition = function (s) {
// "aab"
// ["aa", "b"]
// ["a", "a", "b"]
const list = [];
backtrack(s, list, [], 0);
return list;
};
Python Code:
class Solution:
def partition(self, s: str) -> List[List[str]]:
"""回溯法"""
res = []
def helper(s, tmp):
"""
如果是空字符串，说明已经处理完毕
否则逐个字符往前测试，判断是否是回文
如果是，则处理剩余字符串，并将已经得到的列表作为参数
"""
if not s:
res.append(tmp)
for i in range(1, len(s) + 1):
if s[:i] == s[:i][::-1]:
helper(s[i:], tmp + [s[:i]])
helper(s, [])
return res
CPP Code:
class Solution {
private:
vector<vector<string>> ans;
vector<string> tmp;
bool isPalindrome(string &s, int first, int last) {
while (first < last && s[first] == s[last]) ++first, --last;
return first >= last;
}
void dfs(string &s, int start) {
if (start == s.size()) { ans.push_back(tmp); return; }
for (int i = start; i < s.size(); ++i) {
if (isPalindrome(s, start, i)) {
tmp.push_back(s.substr(start, i - start + 1));
dfs(s, i + 1);
tmp.pop_back();
}
}
}
public:
vector<vector<string>> partition(string s) {
dfs(s, 0);
return ans;
}
};
最近更新 8mo ago