class Solution {
public:
vector<vector<string>> partition(string s) {
}
};
剑指 Offer II 086. 分割回文子字符串
给定一个字符串 s ，请将 s 分割成一些子串，使每个子串都是 回文串 ，返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1：
输入：s = "google" 输出：[["g","o","o","g","l","e"],["g","oo","g","l","e"],["goog","l","e"]]
示例 2：
输入：s = "aab" 输出：[["a","a","b"],["aa","b"]]
示例 3：
输入：s = "a" 输出：[["a"]]
提示：
1 <= s.length <= 16s 仅由小写英文字母组成
注意：本题与主站 131 题相同： https://leetcode.cn/problems/palindrome-partitioning/
原站题解
golang 解法, 执行用时: 224 ms, 内存消耗: 23.2 MB, 提交时间: 2022-11-16 12:49:54
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 解法, 执行用时: 228 ms, 内存消耗: 23.1 MB, 提交时间: 2022-11-16 12:49:37
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.1 MB, 提交时间: 2022-11-16 12:49:17
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 解法, 执行用时: 112 ms, 内存消耗: 32.1 MB, 提交时间: 2022-11-16 12:48:43
class Solution:
def partition(self, s: str) -> List[List[str]]:
'''
f[i][j] 表示 s[i:j]是否为回文字符串
f(i,j) = True, i ≥ j
f(i, j) = f(i+1,j−1) ∧ (s[i]=s[j]), otherwise
'''
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