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 仅由小写英文字母组成相似题目
原站题解
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