新年的刷的第一題，題目如下：
給你一個字串 s，找到 s 中最長的回文子串，
示例 1：
輸入：s = "babad"
輸出："bab"
解釋："aba" 同樣是符合題意的答案，
示例 2：
輸入：s = "cbbd"
輸出："bb"
示例 3：
輸入：s = "a"
輸出："a"
示例 4：
輸入：s = "ac"
輸出："a"
提示：
1 <= s.length <= 1000
s 僅由數字和英文字母（大寫和/或小寫）組成
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
初始思路：
剛開始的想法是想每個字符開始向左右進行拓展，將全部的字符回圈一遍，最后就可以找到最長的回文字串，但自己感覺這種方法時間復雜度太高了，就沒往下想了，唉，太不自信了，
答案思路：
答案寫的非常詳細，分了三種方法，第三種不講，有點復雜，首先要說的是和自己初始子路類似的解法-中心擴展演算法，廢話不多說，直接上代碼：
class Solution { public: pair<int,int> getLongest(string & s,int left,int right) {
/*注意這里是while回圈，會一直向外擴展，知道找到當前字符對應的最長回文串，*/ while(left>=0&&right<s.size()&&s[left]==s[right]) { left--; right++; }
/*對pair的用法不熟悉，還沒想過可以這樣用*/ return {left+1,right-1}; } string longestPalindrome(string s) { int start=0,end=0;
/*看這里，這個for回圈，將每個字符都進行遍歷*/ for(int i=0;i<s.size();i++) {
/*感覺很困惑吧，為啥要將getLongest函式呼叫兩次，我簡單的理解為奇數長度和偶數長度回文串兩種情況，*/ auto [left1,right1]=getLongest(s,i,i); auto [left2,right2]=getLongest(s,i,i+1); if(right1-left1>end-start) { start=left1; end=right1; } if(right2-left2>end-start) { start=left2; end=right2; } }
/*回傳最長的回文字串，答案不唯一*/ return s.substr(start,end-start+1); } };
答案中介紹的第二種方法是動態規劃，直接看代碼：
class Solution { public: string longestPalindrome(string s) { vector<vector<int>> dp(n, vector<int>(n));string strReturn="";
/*從長度1開始，一直到s.size()，注意不要被0誤導*/ for(int len=0;len<s.size();len++) {
/*每種長度下的字符都遍歷一遍賦值*/ for(int i=0;i<s.size()-len;i++) {
/*對應的是字符自己*/ if(len==0) { dp[i][i]=1; }
/*長度1的情況*/ else if(len==1) { dp[i][i+len]=s[i]==s[i+len]; }
/*其他情況*/ else { dp[i][i+len]=dp[i+1][i+len-1]&&(s[i]==s[i+len]); } if(dp[i][i+len]&&len+1>strReturn.size()) { strReturn=s.substr(i,len+1); } } } return strReturn; } };
兩種演算法的時間和空間復雜度對比如下：
時間復雜度 空間復雜度
中心擴展演算法： O（n*n） O（1）
動態規劃： O（n*n） O(n*n)
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/259638.html
標籤：其他
上一篇：還傻傻分不清楚equals和==的區別嗎？看完就明白了
下一篇：npm的一些簡單命令