每日OJ题_回文串dp③_力扣1745. 分割回文串 IV

本文主要是介绍每日OJ题_回文串dp③_力扣1745. 分割回文串 IV，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

力扣1745. 分割回文串 IV

解析代码

---

力扣1745. 分割回文串 IV

1745. 分割回文串 IV

难度 困难

给你一个字符串 s ，如果可以将它分割成三个 非空 回文子字符串，那么返回 true ，否则返回 false 。

当一个字符串正着读和反着读是一模一样的，就称其为 回文字符串 。

示例 1：

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

示例 2：

输入：s = "bcbddxy"
输出：false
解释：s 没办法被分割成 3 个回文子字符串。

提示：

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

class Solution {
public:bool checkPartitioning(string s) {}
};

---

解析代码

        题目要求⼀个字符串被分成三个非空回文子串，一看要表示的状态很多，有些无从下手。 其实可以把它拆成两个小问题：

• 动态规划求解字符串中的一段非空子串是否是回文串。 
• 枚举三个子串除字符串端点外的起止点，查询这三段非空子串是否是回文串。

        那么这道困难题就变为简单题了，变成了一道枚举题。 关于预处理所有子串是否回文，已经在力扣647. 回文子串讲过。

class Solution {
public:bool checkPartitioning(string s) {int n = s.size();vector<vector<bool>> dp(n, vector<bool>(n, false));for(int i = n - 1; i >= 0; --i){for(int j = i; j < n; ++j){if(s[i] == s[j])dp[i][j] = i + 1 >= j ? true : dp[i+1][j-1];}}for(int i = 1; i < n - 1; ++i) // 枚举第二个字符串的开头和结尾{for(int j = i; j < n - 1; ++j){if(dp[0][i - 1] && dp[i][j] && dp[j + 1][n - 1])return true;}}return false;}
};

这篇关于每日OJ题_回文串dp③_力扣1745. 分割回文串 IV的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---