class Solution {
public:
vector<vector<string>> partition(string s) {
}
};
131. 分割回文串
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1：
输入：s = "aab" 输出：[["a","a","b"],["aa","b"]]
示例 2：
输入：s = "a" 输出：[["a"]]
提示：
1 <= s.length <= 16s 仅由小写英文字母组成相似题目
原站题解
cpp 解法, 执行用时: 55 ms, 内存消耗: 70.6 MB, 提交时间: 2025-03-01 10:13:31
class Solution {
bool isPalindrome(string& s, int left, int right) {
while (left < right) {
if (s[left++] != s[right--]) {
return false;
}
}
return true;
}
public:
vector<vector<string>> partition(string s) {
int n = s.length();
vector<vector<string>> ans;
vector<string> path;
// start 表示当前这段回文子串的开始位置
auto dfs = [&](auto&& dfs, int i, int start) {
if (i == n) {
ans.emplace_back(path);
return;
}
// 不选 i 和 i+1 之间的逗号（i=n-1 时一定要选）
if (i < n - 1) {
dfs(dfs, i + 1, start);
}
// 选 i 和 i+1 之间的逗号（把 s[i] 作为子串的最后一个字符）
if (isPalindrome(s, start, i)) {
path.push_back(s.substr(start, i - start + 1));
dfs(dfs, i + 1, i + 1); // 下一个子串从 i+1 开始
path.pop_back(); // 恢复现场
}
};
dfs(dfs, 0, 0);
return ans;
}
};
cpp 解法, 执行用时: 43 ms, 内存消耗: 52.2 MB, 提交时间: 2025-03-01 10:13:12
class Solution {
bool isPalindrome(string& s, int left, int right) {
while (left < right) {
if (s[left++] != s[right--]) {
return false;
}
}
return true;
}
public:
vector<vector<string>> partition(string s) {
int n = s.length();
vector<vector<string>> ans;
vector<string> path;
auto dfs = [&](auto&& dfs, int i) {
if (i == n) {
ans.emplace_back(path);
return;
}
for (int j = i; j < n; j++) { // 枚举子串的结束位置
if (isPalindrome(s, i, j)) {
path.push_back(s.substr(i, j - i + 1));
dfs(dfs, j + 1);
path.pop_back(); // 恢复现场
}
}
};
dfs(dfs, 0);
return ans;
}
};
java 解法, 执行用时: 11 ms, 内存消耗: 55.9 MB, 提交时间: 2025-03-01 10:13:00
class Solution {
private final List<List<String>> ans = new ArrayList<>();
private final List<String> path = new ArrayList<>();
private String s;
public List<List<String>> partition(String s) {
this.s = s;
dfs(0);
return ans;
}
private void dfs(int i) {
if (i == s.length()) {
ans.add(new ArrayList<>(path)); // 复制 path
return;
}
for (int j = i; j < s.length(); j++) { // 枚举子串的结束位置
if (isPalindrome(i, j)) {
path.add(s.substring(i, j + 1));
dfs(j + 1);
path.remove(path.size() - 1); // 恢复现场
}
}
}
private boolean isPalindrome(int left, int right) {
while (left < right) {
if (s.charAt(left++) != s.charAt(right--)) {
return false;
}
}
return true;
}
}
java 解法, 执行用时: 8 ms, 内存消耗: 56.1 MB, 提交时间: 2025-03-01 10:12:44
class Solution {
private final List<List<String>> ans = new ArrayList<>();
private final List<String> path = new ArrayList<>();
private String s;
public List<List<String>> partition(String s) {
this.s = s;
dfs(0, 0);
return ans;
}
// start 表示当前这段回文子串的开始位置
private void dfs(int i, int start) {
if (i == s.length()) {
ans.add(new ArrayList<>(path)); // 复制 path
return;
}
// 不选 i 和 i+1 之间的逗号（i=n-1 时一定要选）
if (i < s.length() - 1) {
dfs(i + 1, start);
}
// 选 i 和 i+1 之间的逗号（把 s[i] 作为子串的最后一个字符）
if (isPalindrome(start, i)) {
path.add(s.substring(start, i + 1));
dfs(i + 1, i + 1); // 下一个子串从 i+1 开始
path.remove(path.size() - 1); // 恢复现场
}
}
private boolean isPalindrome(int left, int right) {
while (left < right) {
if (s.charAt(left++) != s.charAt(right--)) {
return false;
}
}
return true;
}
}
javascript 解法, 执行用时: 188 ms, 内存消耗: 60.2 MB, 提交时间: 2023-01-12 09:56:30
/**
* @param {string} s
* @return {string[][]}
*/
var partition = function(s) {
const dfs = (i) => {
if (i === n) {
ret.push(ans.slice());
return;
}
for (let j = i; j < n; ++j) {
if (isPalindrome(i, j) === 1) {
ans.push(s.slice(i, j + 1));
dfs(j + 1);
ans.pop();
}
}
}
// 记忆化搜索中，f[i][j] = 0 表示未搜索，1 表示是回文串，-1 表示不是回文串
const isPalindrome = (i, j) => {
if (f[i][j] !== 0) {
return f[i][j];
}
if (i >= j) {
f[i][j] = 1;
} else if (s[i] === s[j]) {
f[i][j] = isPalindrome(i + 1, j - 1);
} else {
f[i][j] = -1;
}
return f[i][j];
}
const n = s.length;
const ret = [], ans = [];
const f = new Array(n).fill(0).map(() => new Array(n).fill(0));
dfs(0);
return ret;
};
javascript 解法, 执行用时: 196 ms, 内存消耗: 60.1 MB, 提交时间: 2023-01-12 09:55:57
/**
* @param {string} s
* @return {string[][]}
*/
var partition = function(s) {
const dfs = (i) => {
if (i === n) {
ret.push(ans.slice());
return;
}
for (let j = i; j < n; ++j) {
if (f[i][j]) {
ans.push(s.slice(i, j + 1));
dfs(j + 1);
ans.pop();
}
}
}
const n = s.length;
const f = new Array(n).fill(0).map(() => new Array(n).fill(true));
let ret = [], ans = [];
for (let i = n - 1; i >= 0; --i) {
for (let j = i + 1; j < n; ++j) {
f[i][j] = (s[i] === s[j]) && f[i + 1][j - 1];
}
}
dfs(0);
return ret;
};
golang 解法, 执行用时: 232 ms, 内存消耗: 22 MB, 提交时间: 2023-01-12 09:55:34
func partition(s string) (ans [][]string) {
n := len(s)
f := make([][]bool, n)
for i := range f {
f[i] = make([]bool, n)
for j := range f[i] {
f[i][j] = true
}
}
for i := n - 1; i >= 0; i-- {
for j := i + 1; j < n; j++ {
f[i][j] = s[i] == s[j] && f[i+1][j-1]
}
}
splits := []string{}
var dfs func(int)
dfs = func(i int) {
if i == n {
ans = append(ans, append([]string(nil), splits...))
return
}
for j := i; j < n; j++ {
if f[i][j] {
splits = append(splits, s[i:j+1])
dfs(j + 1)
splits = splits[:len(splits)-1]
}
}
}
dfs(0)
return
}
golang 解法, 执行用时: 232 ms, 内存消耗: 23.1 MB, 提交时间: 2023-01-12 09:54:51
func partition(s string) (ans [][]string) {
n := len(s)
f := make([][]int8, n)
for i := range f {
f[i] = make([]int8, n)
}
// 0 表示尚未搜索，1 表示是回文串，-1 表示不是回文串
var isPalindrome func(i, j int) int8
isPalindrome = func(i, j int) int8 {
if i >= j {
return 1
}
if f[i][j] != 0 {
return f[i][j]
}
f[i][j] = -1
if s[i] == s[j] {
f[i][j] = isPalindrome(i+1, j-1)
}
return f[i][j]
}
splits := []string{}
var dfs func(int)
dfs = func(i int) {
if i == n {
ans = append(ans, append([]string(nil), splits...))
return
}
for j := i; j < n; j++ {
if isPalindrome(i, j) > 0 {
splits = append(splits, s[i:j+1])
dfs(j + 1)
splits = splits[:len(splits)-1]
}
}
}
dfs(0)
return
}
python3 解法, 执行用时: 116 ms, 内存消耗: 31.2 MB, 提交时间: 2022-11-16 12:54:51
class Solution:
def partition(self, s: str) -> List[List[str]]:
n = len(s)
ret = list()
ans = list()
@cache
def isPalindrome(i: int, j: int) -> int:
if i >= j:
return 1
return isPalindrome(i + 1, j - 1) if s[i] == s[j] else -1
def dfs(i: int):
if i == n:
ret.append(ans[:])
return
for j in range(i, n):
if isPalindrome(i, j) == 1:
ans.append(s[i:j+1])
dfs(j + 1)
ans.pop()
dfs(0)
isPalindrome.cache_clear()
return ret
python3 解法, 执行用时: 108 ms, 内存消耗: 32 MB, 提交时间: 2022-11-16 12:54:28
class Solution:
def partition(self, s: str) -> List[List[str]]:
n = len(s)
f = [[True] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
for j in range(i + 1, n):
f[i][j] = (s[i] == s[j]) and f[i + 1][j - 1]
ret = list()
ans = list()
def dfs(i: int):
if i == n:
ret.append(ans[:])
return
for j in range(i, n):
if f[i][j]:
ans.append(s[i:j+1])
dfs(j + 1)
ans.pop()
dfs(0)
return ret