class Solution {
public:
bool checkPartitioning(string s) {
}
};
1745. 回文串分割 IV
给你一个字符串 s ，如果可以将它分割成三个 非空 回文子字符串，那么返回 true ，否则返回 false 。
当一个字符串正着读和反着读是一模一样的，就称其为 回文字符串 。
示例 1：
输入：s = "abcbdd" 输出：true 解释："abcbdd" = "a" + "bcb" + "dd"，三个子字符串都是回文的。
示例 2：
输入：s = "bcbddxy" 输出：false 解释：s 没办法被分割成 3 个回文子字符串。
提示：
3 <= s.length <= 2000s 只包含小写英文字母。原站题解
golang 解法, 执行用时: 36 ms, 内存消耗: 10.9 MB, 提交时间: 2023-08-18 15:39:20
func checkPartitioning(s string) bool {
n := len(s)
dp := make([][]bool, n)
for i := range dp {
dp[i] = make([]bool, n)
}
for i := n - 1; i >= 0; i-- {
for j := i; j < n; j++ {
dp[i][j] = s[i] == s[j] && (i + 1 >= j - 1 || dp[i+1][j-1]);
}
}
for i := 1; i < n; i++ {
if !dp[0][i-1] {
continue
}
for j := i; j < n - 1; j++ {
if dp[i][j] && dp[j+1][n-1] {
return true
}
}
}
return false
}
golang 解法, 执行用时: 844 ms, 内存消耗: 13.4 MB, 提交时间: 2023-08-18 15:38:45
func is(a string) bool {
for i := 0; i < len(a)/2; i++ {
if a[i] != a[len(a)-1-i] {
return false
}
}
return true
}
func checkPartitioning(s string) bool {
cache := make(map[string]bool)
for i := 1; i < len(s); i++ {
current := 0
for j := i+1; j < len(s); j++ {
current ^= 1<<(s[j-1]-'a')
if current !=0 && current&(current-1)!=0{
continue
}
l,m,r:=s[:i],s[i:j],s[j:]
if _,ok:=cache[l];!ok{
cache[l]=is(l)
}
if _,ok:=cache[m];!ok{
cache[m]=is(m)
}
if _,ok:=cache[r];!ok{
cache[r]=is(r)
}
if cache[l]&&cache[m]&&cache[r]{
return true
}
}
}
return false
}
python3 解法, 执行用时: 116 ms, 内存消耗: 16.3 MB, 提交时间: 2023-08-18 15:38:00
class Manacher:
def __init__(self, string=''):
self.string = string
def add_char(self):
add_string = '^'
for char in self.string:
add_string += '@' + char
add_string += '@*'
return add_string
def get_p(self):
self.add_string = self.add_char()
self.P = [0] * len(self.add_string)
R, mid = 0, 0
for i in range(1, len(self.add_string)-1):
self.P[i] = min(self.P[mid*2-i], R-i) if R > i else 0
while self.add_string[i+1+self.P[i]] == self.add_string[i-1-self.P[i]]:
self.P[i] +=1
if i + self.P[i] > R:
R = i + self.P[i]
mid = i
return self.P
def check_partition_s(self, l, r): # 判断在串S的区间[l,r]的子串是否为回文串。
l, r = l * 2 + 2, r * 2 + 2
mid = (l + r) // 2
return self.P[mid] > r - mid
class Solution:
def checkPartitioning(self, s: str) -> bool:
manacher = Manacher(s)
manacher.get_p()
n = len(s)
pre, suf = [], []
pre_vis = [0] * n
suf_vis = [0] * n
for i in range(0, n):
if manacher.check_partition_s(0, n-1-i):
pre.append(n-i-1)
pre_vis[n-i-1] = 1
if manacher.check_partition_s(i, n-1):
suf.append(i)
suf_vis[i] = 1
suf_n, cnt = len(suf), 0
for i in range(n):
if pre_vis[i]:
while cnt < suf_n and suf[cnt] < i + 2:
cnt +=1
if cnt < suf_n and manacher.check_partition_s(i+1, suf[cnt]-1):
return True
# print(pre, suf, pre_vis, suf_vis)
pre_n, cnt = len(pre), 0
for i in range(n-1, 0, -1):
if suf_vis[i]:
while cnt < pre_n and pre[cnt] + 2 > i:
cnt +=1
if cnt < pre_n and manacher.check_partition_s(pre[cnt]+1, i-1):
return True
return False