## 题目地址

https://leetcode.com/problems/palindrome-partitioning/

## 题目描述

Given a string s , partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example:

``````Input: "aab"
Output:
[
["aa","b"],
["a","a","b"]
]
``````

## 思路

``````class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> res;
vector<string> out;
helper(s, 0, out, res);
return res;
}
void helper(string s, int start, vector<string>& out, vector<vector<string>>& res) {
if (start == s.size()) { res.push_back(out); return; }
for (int i = start; i < s.size(); ++i) {
if (!isPalindrome(s, start, i)) continue;
out.push_back(s.substr(start, i - start + 1));
helper(s, i + 1, out, res);
out.pop_back();
}
}
bool isPalindrome(string s, int start, int end) {
while (start < end) {
if (s[start] != s[end]) return false;
++start; --end;
}
return true;
}
};
``````

``````class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> res;
if (s.empty()) return {{}};
for (int i = 0; i < s.size(); ++i) {
if (!isPalindrome(s, i + 1)) continue;
for (auto list : partition(s.substr(i + 1))) {
list.insert(list.begin(), s.substr(0, i + 1));
res.push_back(list);
}
}
return res;
}
bool isPalindrome(string s, int n) {
for (int i = 0; i < n / 2; ++i) {
if (s[i] != s[n - 1 - i]) return false;
}
return true;
}
};
``````

``````class Solution {
public:
vector<vector<string>> partition(string s) {
int n = s.size();
vector<vector<string>> res;
vector<string> out;
vector<vector<bool>> dp(n, vector<bool>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= i; ++j) {
if (s[i] == s[j] && (i - j <= 2 || dp[j + 1][i - 1])) {
dp[j][i] = true;
}
}
}
helper(s, 0, dp, out, res);
return res;
}
void helper(string s, int start, vector<vector<bool>>& dp, vector<string>& out, vector<vector<string>>& res) {
if (start == s.size()) { res.push_back(out); return; }
for (int i = start; i < s.size(); ++i) {
if (!dp[start][i]) continue;
out.push_back(s.substr(start, i - start + 1));
helper(s, i + 1, dp, out, res);
out.pop_back();
}
}
};
``````

``````class Solution {
public:
vector<vector<string>> partition(string s) {
int n = s.size();
vector<vector<vector<string>>> res(n + 1);
res[0].push_back({});
vector<vector<bool>> dp(n, vector<bool>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= i; ++j) {
if (s[i] == s[j] && (i - j <= 2 || dp[j + 1][i - 1])) {
dp[j][i] = true;
string cur = s.substr(j, i - j + 1);
for (auto list : res[j]) {
list.push_back(cur);
res[i + 1].push_back(list);
}
}
}
}
return res[n];
}
};
``````

• 回溯法

## 代码

• 语言支持：JS，Python3
``````

/*
* @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;
};

``````
``````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
``````

评论
0 评论