当前位置：首页 > news >正文

LeetCode：DP-回文串问题

news 2025/5/2 6:47:37

中等

5. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
提示：

1 <= s.length <= 1000
s 仅由数字和英文字母组成

string longestPalindrome(string s) {int n = s.size();// i开始j结尾的子串是否回文vector<vector<bool>> dp(n, vector<bool>(n));int begin, len = 0;for (int i = n - 1; i >= 0; --i) {for (int j = i; j < n; ++j) {if (s[i] == s[j]) {dp[i][j] = j-i+1 > 2 ? dp[i+1][j-1] : true;}if (dp[i][j] == true && j-i+1 > len) {len = j-i+1;begin = i;}}}return s.substr(begin, len);
}

516. 最长回文子序列

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：
输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。
示例 2：
输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。
提示：

1 <= s.length <= 1000
s 仅由小写英文字母组成

int longestPalindromeSubseq(string s) {int n = s.size();// i开始j结尾的最长回文子序列vector<vector<int>> dp(n, vector<int>(n));for (int i = n - 1; i >= 0; --i) {dp[i][i] = 1;for (int j = i + 1; j < n; ++j) {if (s[i] == s[j]) {dp[i][j] = dp[i+1][j-1] + 2;} else {dp[i][j] = max(dp[i+1][j], dp[i][j-1]);}}}return dp[0][n - 1];
}

647. 回文子串

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

示例 1：
输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"
示例 2：
输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
提示：

1 <= s.length <= 1000
s 由小写英文字母组成

int countSubstrings(string s) {int n = s.size();// i开始j结尾的子串是否回文vector<vector<bool>> dp(n, vector<bool>(n));int ans = 0;for (int i = n - 1; i >= 0; --i) {for (int j = i; j < n; ++j) {if (s[i] == s[j]) {dp[i][j] = j-i+1 > 2 ? dp[i+1][j-1] : true;}if (dp[i][j] == true) {ans++;}}}return ans;
}

困难

132. 分割回文串 II

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。

返回符合要求的 最少分割次数 。

示例 1：
输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
示例 2：
输入：s = "a"
输出：0
示例 3：
输入：s = "ab"
输出：1
提示：

1 <= s.length <= 2000
s 仅由小写英文字母组成

int minCut(string s) {int n = s.size();// i开始j结尾的子串是否回文vector<vector<bool>> check(n, vector<bool>(n));for (int i = n - 1; i >= 0; i--) {for (int j = i; j < n; j++) {if (s[i] == s[j]) {check[i][j] = j-i+1 > 2 ? check[i + 1][j - 1] : true;}}}// i结尾的最少分割次数vector<int> dp(n, INT_MAX);dp[0] = 0;for (int i = 1; i < n; ++i) {if (check[0][i] == true) {dp[i] = 0;continue;}for (int j = 0; j < i; ++j) {if (check[j+1][i]) {dp[i] = min(dp[i], dp[j] + 1);}}}return dp[n - 1];
}

1278. 分割回文串 III

给你一个由小写字母组成的字符串 s，和一个整数 k。

请你按下面的要求分割字符串：

首先，你可以将 s 中的部分字符修改为其他的小写英文字母。
接着，你需要把 s 分割成 k 个非空且不相交的子串，并且每个子串都是回文串。

请返回以这种方式分割字符串所需修改的最少字符数。

示例 1：
输入：s = "abc", k = 2
输出：1
解释：你可以把字符串分割成 "ab" 和 "c"，并修改 "ab" 中的 1 个字符，将它变成回文串。
示例 2：
输入：s = "aabbc", k = 3
输出：0
解释：你可以把字符串分割成 "aa"、"bb" 和 "c"，它们都是回文串。
示例 3：
输入：s = "leetcode", k = 8
输出：0
提示：

1 <= k <= s.length <= 100
s 中只含有小写英文字母。

int palindromePartition(string s, int k) {int n = s.size();// i-1结尾，分割为j个，所需修改的最少字符数vector<vector<int>> dp(n+1, vector<int>(k+1, INT_MAX));dp[0][0] = 0;for (int i = 1; i <= n; ++i) {for (int j = 1; j <= min(k, i); ++j) {if (j == 1) {dp[i][j] = cost(s, 0, i - 1);} else {// z从(j-1+1)-1开始，表示前面的j-1个子串for (int z = j - 1; z < i; ++z) {dp[i][j] = min(dp[i][j], dp[z][j-1] + cost(s, z, i-1));}}}}return dp[n][k];
}int cost(const string& s, int left, int right) {int ret = 0;while (left < right) {if (s[left] != s[right]) {ret++;}left++, right--;}return ret;
}

1312. 让字符串成为回文串的最少插入次数

给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。

请你返回让 s 成为回文串的 最少操作次数 。

「回文串」是正读和反读都相同的字符串。

示例 1：
输入：s = "zzazz"
输出：0
解释：字符串 "zzazz" 已经是回文串了，所以不需要做任何插入操作。
示例 2：
输入：s = "mbadm"
输出：2
解释：字符串可变为 "mbdadbm" 或者 "mdbabdm" 。
示例 3：
输入：s = "leetcode"
输出：5
解释：插入 5 个字符后字符串变为 "leetcodocteel" 。
提示：

1 <= s.length <= 500
s 中所有字符都是小写字母。

int minInsertions(string s) {int n = s.size();// i开始j结尾的最少插入次数vector<vector<int>> dp(n, vector<int>(n));for (int i = n - 1; i >= 0; --i) {dp[i][i] = 0;for (int j = i + 1; j < n; ++j) {if (s[i] == s[j]) {dp[i][j] = dp[i+1][j-1];} else {dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1;}}}return dp[0][n - 1];
}

1745. 分割回文串 IV

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

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

示例 1：
输入：s = "abcbdd"
输出：true
解释："abcbdd" = "a" + "bcb" + "dd"，三个子字符串都是回文的。
示例 2：
输入：s = "bcbddxy"
输出：false
解释：s 没办法被分割成 3 个回文子字符串。
提示：

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

bool checkPartitioning(string s) {int n = s.size();// i开始j结尾的子串是否回文vector<vector<bool>> dp(n, vector<bool>(n));for (int i = n - 1; i >= 0; i--) {for (int j = i; j < n; j++) {if (s[i] == s[j]) {dp[i][j] = j-i+1 > 2 ? dp[i + 1][j - 1] : true;}}}// 枚举三个区间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;
}