网站ftp需要关闭,wordpress动态,正能量网站ip,html文件编辑器647 回文子串
给定一个字符串#xff0c;你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串#xff0c;即使是由相同的字符组成#xff0c;也会被视作不同的子串。
方法一#xff1a;动态规划#xff1a;
采用一个二维的dp数组#xf…647 回文子串
给定一个字符串你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串即使是由相同的字符组成也会被视作不同的子串。
方法一动态规划
采用一个二维的dp数组dp的含义是从i到j闭区间里的字符串是否是回文串。每次进行比较如果i和j相等相邻或者只差一位此时判断的这个肯定是回文子串如果相差2以上内层是回文串的话外层肯定还是回文串注意遍历顺序由于递推公式的影响得从左下到右上遍历
class Solution {
public:int countSubstrings(string s) {vectorvectorbool dp(s.size(), vectorbool(s.size(), false));int result 0;for (int i s.size() - 1; i 0; i--) { // 注意遍历顺序for (int j i; j s.size(); j) {if (s[i] s[j]) {if (j - i 1) { // 情况一 和 情况二result;dp[i][j] true;} else if (dp[i 1][j - 1]) { // 情况三result;dp[i][j] true;}}}}return result;}
}; 方法二双指针
从内往外判断从中心扩散到两边
class Solution {
public:int countSubstrings(string s) {int result 0;for (int i 0; i s.size(); i) {result extend(s, i, i, s.size()); // 以i为中心result extend(s, i, i 1, s.size()); // 以i和i1为中心}return result;}int extend(const string s, int i, int j, int n) {int res 0;while (i 0 j n s[i] s[j]) {i--;j;res;}return res;}
};
516 最长回文子序列
给定一个字符串 s 找到其中最长的回文子序列并返回该序列的长度。可以假设 s 的最大长度为 1000 。
示例 1: 输入: bbbab 输出: 4 一个可能的最长回文子序列为 bbbb。
示例 2: 输入:cbbd 输出: 2 一个可能的最长回文子序列为 bb。
本题要看最长回文子序列首先dp数组里的值为i到j最长回文子序列的长度递推公式要看i和j是否相等相等的话就是里面的长度加上外面两个的长度2不相等的话就是分别算两个单的元素取大的初始化时注意要找到根基也就是i和j相等的情况此时初始化值为1遍历顺序根据递推公式来看也就是从左下往右上角遍历
class Solution {
public:int longestPalindromeSubseq(string s) {vectorvectorint dp(s.size(), vectorint(s.size(), 0));for (int i 0; i s.size(); i) {dp[i][i] 1;}for (int i s.size() - 1; i 0; i--) {for (int j i 1; j s.size(); 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][s.size() - 1];}
};
