网站图片展示代码,最新新闻事件摘抄,福州app制作公司,百度获客平台最长回文子串
给你一个字符串 s#xff0c;找到 s 中最长的 回文 子串。
https://leetcode.cn/problems/longest-palindromic-substring/submissions/607962358/ 动态规划#xff1a; 回文串即是从前面开始读和从后面开始读#xff0c;读出来的字符串均相同的字符串#…最长回文子串
给你一个字符串 s找到 s 中最长的 回文 子串。
https://leetcode.cn/problems/longest-palindromic-substring/submissions/607962358/ 动态规划 回文串即是从前面开始读和从后面开始读读出来的字符串均相同的字符串可以理解字符串正中间是一面镜子镜子的两侧字符串必然对称。 实际上回文串如果只含一个字符必然是回文串如果含2个字符若两个字符相等则必然是回文串否则不是回文串例如ab这就不是回文串‘bb’就是 如果含多个字符那么如果第一位和最后一位字符不相同那肯定不是回文串按照上图所示回文串必然是对称的如果第一位和最后一位字符不同那么就必然存在不对称的情况了 如果含多个字符且第一位和最后一位字符相同那么如果它去除掉第一位和最后一位字符后依然是回文串那它肯定是回文串否则如果它去除掉第一位和最后一位字符后不是回文串那说明这个子串肯定不对称不对称的话肯定就不是回文串了。所以问S[i,j]是不是字串就要看它的子串S[i1,j-1]是不是回文串。显然应该用动态规划。 动态规划访问数组的时候一定要按照图里面的。1斜线2斜线3斜线……5斜线这个顺序去访问 否则例如下面图示的这个访问顺序会出现访问dp[0,3]时dp[1,2] 没赋值就访问的问题 vector最好用intvectorvectorint别用布尔bool否则难以察觉到自己的算法是否有数组越界的问题。
class Solution {
public:string longestPalindrome(string s) {int s_len s.size();if (s_len 1) {return s;}int max_len 1, begin 0; // 最大回文长度和起始位置vectorvectorint dp(s_len, vectorint(s_len));// S[i][i]也就是串的i号位字符由于所有长度为1的串都是回文所以是truefor (int i 0; i s_len; i) {dp[i][i] true;}// 由于s[i][j]回文取决于S[i1][j-1]是否是回文所以优先填充斜线// 当前检测的子串长度为Lfor (int L 2; L s_len; L) {for (int i 0; i s_len; i) {int j L i - 1;if (j s_len)//子串终点标记j不能大于父串break;if (s[i] s[j]) {//看看字串是否是回文串if (j - i 1 2) {//长度2又有s[i] s[j],必然是回文串dp[i][j] true;} else {dp[i][j] dp[i 1][j - 1];}} else {// s[i] ! s[j]出现了不对称的情况不可能是回文串了dp[i][j] false;}if (dp[i][j] max_len j - i 1) {// 此次迭代检测到回文串更新最大值begin i;max_len j - i 1;}}}return s.substr(begin, max_len);}
};
