【LetMeFly】1745.分割回文串 IV：動態規劃（用III或II能直接秒）

力扣題目鏈接：https://leetcode.cn/problems/palindrome-partitioning-iv/

給你一個字符串?s?，如果可以將它分割成三個?非空?回文子字符串，那么返回?true?，否則返回?false?。

當一個字符串正著讀和反著讀是一模一樣的，就稱其為 回文字符串 。

?

示例 1：

輸入：s = "abcbdd"
輸出：true
解釋："abcbdd" = "a" + "bcb" + "dd"，三個子字符串都是回文的。

示例 2：

輸入：s = "bcbddxy"
輸出：false
解釋：s 沒辦法被分割成 3 個回文子字符串。

?

提示：

• 3 <= s.length <= 2000
• s?????? 只包含小寫英文字母。

解題方法：動態規劃

如果想用之前的方法直接AC：

• 1278.分割回文串 III：令k = 3，復雜度$O(n^{2}k)$
• 132.分割回文串 II：也就是今天的方法。

在132.分割回文串 II中我們通過預處理可以在$O(n^2)$時間復雜度內得到字符串s的任一字串是否為回文串（方法簡述如下：）

使用isok[i][j]表示字符串s從下標i到下標j的子串是否為回文串。若$i\ge j$則視為回文串，否則有狀態轉移方程$isok[i][j]=s[i]==s[j]\text{?AND?}isok[i+1][j?1]$。

都知道任意一個字串是否是回文串了，我直接枚舉兩個分割位置，每次使用$O(1)$時間看看被分成的三段是否都為回文字符串不就可以了么？

• 時間復雜度$O(n^2)$，其中$n=len(s)$
• 空間復雜度$O(n^2)$

AC代碼

C++

/** @Author: LetMeFly* @Date: 2025-03-04 10:18:19* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-03-04 10:28:38*/
class Solution {
public:bool checkPartitioning(string s) {int n = s.size();vector<vector<bool>> isok(n, vector<bool>(n, true));for (int i = n - 1; i >= 0; i--) {for (int j = i + 1; j < n; j++) {isok[i][j] = s[i] == s[j] && isok[i + 1][j - 1];}}for (int i = 0; i < n; i++) {for (int j = i + 1; j < n - 1; j++) {if (isok[0][i] && isok[i + 1][j] && isok[j + 1][n - 1]) {return true;}}}return false;}
};

Python

'''
Author: LetMeFly
Date: 2025-03-04 10:30:23
LastEditors: LetMeFly.xyz
LastEditTime: 2025-03-04 10:33:30
'''
class Solution:def checkPartitioning(self, s: str) -> bool:n = len(s)isok = [[True] * n for _ in range(n)]for i in range(n - 1, -1, -1):for j in range(i + 1, n):isok[i][j] = s[i] == s[j] and isok[i + 1][j - 1]for i in range(n):for j in range(i + 1, n - 1):if isok[0][i] and isok[i + 1][j] and isok[j + 1][n - 1]:return Truereturn False

Go

/** @Author: LetMeFly* @Date: 2025-03-04 10:42:05* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-03-04 10:46:32*/
package mainfunc checkPartitioning(s string) bool {n := len(s)isok := make([][]bool, n)for i, _ := range isok {isok[i] = make([]bool, n)for j, _ := range isok[i] {isok[i][j] = true}}for i := n - 1; i >= 0; i-- {for j := i + 1; j < n; j++ {isok[i][j] = s[i] == s[j] && isok[i + 1][j - 1]}}for i := 0; i < n; i++ {for j := i + 1; j < n - 1; j++ {if isok[0][i] && isok[i + 1][j] && isok[j + 1][n - 1] {return true}}}return false
}

Java

/** @Author: LetMeFly* @Date: 2025-03-04 10:47:02* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-03-04 10:49:14*/
class Solution {public boolean checkPartitioning(String s) {int n = s.length();boolean[][] isok = new boolean[n][n];for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {isok[i][j] = true;}}for (int i = n - 1; i >= 0; i--) {for (int j = i + 1; j < n; j++) {isok[i][j] = s.charAt(i) == s.charAt(j) && isok[i + 1][j - 1];}}for (int i = 0; i < n; i++) {for (int j = i + 1; j < n - 1; j++) {if (isok[0][i] && isok[i + 1][j] && isok[j + 1][n - 1]) {return true;}}}return false;}
}

同步發文于CSDN和我的個人博客，原創不易，轉載經作者同意后請附上原文鏈接哦~

千篇源碼題解已開源