网站外的seo,aspcms网站,重庆网站建设夹夹虫负责,上海做网站优化动态规划-最长回文子串 原题描述解答中心移动思想代码实现复杂度分析时间复杂度空间复杂度 动态规划思想代码实现复杂度分析时间复杂度空间复杂度 突然觉得很有必要将学过的内容记录下来#xff0c;这样后续在需要用到的时候就可以避免从头进行学习#xff0c;而去看自己之前… 动态规划-最长回文子串 原题描述解答中心移动思想代码实现复杂度分析时间复杂度空间复杂度 动态规划思想代码实现复杂度分析时间复杂度空间复杂度 突然觉得很有必要将学过的内容记录下来这样后续在需要用到的时候就可以避免从头进行学习而去看自己之前做过的笔记无疑是效率更高的方法。 而作为计算机专业的学生纸质笔记无法很好的进行记录像写代码、画图、画表都是很麻烦的而且纸质的很容易丢因此还是进行电子笔记记录更佳。
那么选择用博客还是云笔记呢私以为选择更为公开的博客可以更加驱动自己进行详细的记录和进行浅显易懂的讲解从而避免自己某些时候滥竽充数的行为。
原题描述
5. 最长回文子串 给你一个字符串 s找到 s 中最长的回文子串。 如果字符串的反序与原始字符串相同则该字符串称为回文字符串。 示例 1 输入s “babad” 输出“bab” 解释“aba” 同样是符合题意的答案。 示例 2 输入s “cbbd” 输出“bb” 提示 1 s.length 1000 s 仅由数字和英文字母组成 解答
中心移动
思想
对于这个题来说进行最长回文子串的判断首先想到的就是遍历所有的回文子串然后记录最长的回文子串及其长度。 那么如何遍历这些回文子串由于回文子串的遍历需要从中心往四周进行遍历所以需要遍历所有的回文中心但是回文中心会有以下两种情况。
中心只有一个字符的总长度为奇数的情况例如aba中心会有两个字符的总长度为偶数的情况例如abba
设i, j为中心点。那么对于中心只有一个字符的情况1来说ij对于中心会有两个字符的情况2来说ji1。
那其实就很简单了让i、j进行这种遍历在遍历的时候分别设置两个指针l和r进行左右的拓展如果是回文子串就记录否则在当下的回文中心下已经不可能有更长的回文了进行下一次的回文中心遍历即可。
代码实现
class Solution {
public:string longestPalindrome(string s) {int len s.length();if(len 2) // 特殊情况处理return s;int i0, j1;int maxLen 1, startPos 0;while(ilen-1 jlen){if(s[i] s[j]){int left i-1, right j1;while(left0 rightlen-1 s[left]s[right]){left--;right;}if(right-left-1maxLen){maxLen right-left-1;startPos left1;}}if(i!j)i;elsej;}return s.substr(startPos, maxLen);}
};
这里在进行实现的时候有进行一些小tips优化
i从0开始到len-2j从1开始到len-1也就是省略了i0,j0和ilen-1,jlen-1的情况。 因为这两种情况其实也只能判断一个长度为1的回文子串这种情况在中间的时候随便都能判断出来。最极端情况下例如ab这样长度为2的非回文串由于startPos和maxLen的设置最后返回的也是a不会出问题。中途对最长的回文子串进行记录的时候不要直接进行截断来存字符串而是记录开始的下标和长度这样最后只截取一次避免性能开销。
复杂度分析
时间复杂度
令字符串长度为n中心只有一个字符的有n种情况中心有两个字符的有n-1种情况。总共有2n-1种中心情况。 对于每次的中心情况进行遍历的时候由于是向两边扩展最多不超过n/2。 相乘也就是O(n^2)的时间复杂度。
空间复杂度
没有开辟额外空间O(1)
动态规划
动态规划说实话在这个题目并不合适还不如上面的中心移动的方法。因为动态规划相比来说会有额外的二维数组的空间开销。
思想
用最经典的动态规划思考方式来进行。设置一个二维数组dp[n][n]其中dp[i][j]代表s[i...j]是不是回文子串是的话为true不是为false。
最优子结构 s[i...j]是不是回文子串取决于s[i1...j-1]是不是回文子串和s[i]是否与s[j]相同。状态转移方程 d p [ i ] [ j ] { d p [ i 1 ] [ j − 1 ] , s [ i ] s [ j ] f a l s e , s [ i ] ! s [ j ] dp[i][j] \begin{cases} dp[i1][j-1], s[i]s[j]\\ false, s[i]!s[j] \\ \end{cases} dp[i][j]{dp[i1][j−1],false,s[i]s[j]s[i]!s[j]
边界处理 当ij的时候长度为1必定是回文子串dp[i][j]true
代码实现
class Solution {
public:string longestPalindrome(string s) {int len s.length();// 特殊处理if(len 2)return s;int maxLen 1, begin 0;vectorvectorbool dp(len, vectorbool(len, false));for(int i0; ilen; i)dp[i][i] true;for(int j1; jlen; j){for(int i0; ij; i){ // 注意i从0开始if(s[i] ! s[j])dp[i][j] false;else{if(j-i 3)dp[i][j] true;elsedp[i][j] dp[i1][j-1];}if(dp[i][j] true j-i1maxLen){begin i;maxLen j-i1;}}}return s.substr(begin, maxLen);}
};tips: 当s[i] s[j]的时候先进行了j-i3的判断这种情况是子串的长度3的情况在这种情况下s[i]s[j]不管长度为2还是3都是回文子串直接返回true。
复杂度分析
时间复杂度
O(n^2)
空间复杂度
开辟了一个二维数组O(n^2) 2024/03/31 希望后面在刷算法题的时候能够坚持下来在搞懂一个算法题之后通过博客的方式来做笔记这样后面在warmup的时候很快就能上手避免重复的0到1的思考。
