目錄
最長回文子串
驗證回文串
驗證回文串II
回文字串
對應letecode鏈接：
力扣
題目描述：
給你一個字串 s，找到 s 中最長的回文子串，
示例 1：
輸入：s = "babad"
輸出："bab"
解釋："aba" 同樣是符合題意的答案，
示例 2：輸入：s = "cbbd"
輸出："bb"
示例 3：輸入：s = "a"
輸出："a"
示例 4：輸入：s = "ac"
輸出："a"提示：
1 <= s.length <= 1000
s 僅由數字和英文字母（大寫和/或小寫）組成
💖思考方式：1.中心擴散法
根據回文子串的定義：從左往右看和從右往左看都是一樣的這讓我們很容易就想到了中心擴散法，中心擴散法的基本思想是：遍歷每一個下標，以這個下標為中心，利用「回文串」中心對稱的特點，往兩邊擴散，看最多能擴散多遠，
注意：
細節：回文串在長度為奇數和偶數的時候，「回文中心」的形態不一樣：
奇數回文串的「中心」是一個具體的字符，例如：回文串 "aba" 的中心是字符 "b"；
偶數回文串的「中心」是位于中間的兩個字符的「空隙」，例如：回文串 "abba" 的中心是兩個 "b"，也可以看成兩個 "b" 中間的空隙，
我們看一下一個字串可能的回文子串的中心在哪里？
因此我們可以設計一個方法，兼容以上兩種情況：
如果傳入重合的下標，進行中心擴散，此時得到的回文子串的長度是奇數；
如果傳入相鄰的下標，進行中心擴散，此時得到的回文子串的長度是偶數，
string longestPalindrome(string s) { int n=s.size(); if(n==0||n==1)return s;//一個字符直接回傳 for(int i=1;i<n;i++){ help(s,i,i,n);//單個字母為中心 help(s,i-1,i,n);//兩個字母為中心 } return s.substr(ans[0],ans[1]-ans[0]);//回傳最長回文字串的長度 }
向兩邊擴散：
對應代碼：
void help(string&s,int start,int end,int n){ //向兩邊擴散 while(start>=0&&end<=n-1){ if(s[start]==s[end]){ end++; start--; } else{ break; } } if(end-(start+1)>(ans[1]-ans[0])){ ans[0]=start+1; ans[1]=end; } }
可能會有老鐵會說為什么是start+1了?別急博主馬上解釋：
此時當擴散結束之后最長的回文字串是bb而我們start的位置剛好是最長回文字串起始位置的前一個位置所以我們需要將start+1,而最長回文字串的長度剛好是end-start+1.
代碼匯總：
class Solution { public: int ans[2]={0}; string longestPalindrome(string s) { int n=s.size(); if(n==0||n==1)return s;//一個字符直接訪問 for(int i=1;i<n;i++){ help(s,i,i,n);//一個字母為中心向兩邊擴散 help(s,i-1,i,n);//兩個字母為中心向兩步擴散 } return s.substr(ans[0],ans[1]-ans[0]); } void help(string&s,int start,int end,int n){ //向兩邊擴散 while(start>=0&&end<=n-1){ if(s[start]==s[end]){ end++; start--; } else{ break; } } if(end-(start+1)>(ans[1]-ans[0])){ ans[0]=start+1; ans[1]=end; } } };
方法2動態規劃：
思路：定義dp[i][j]表示子串i～j是否是回文子串，回圈s的子串，看是否滿足s[i]，s[j]相等，如果相等，則dp[i][j]是否為回文串取決于dp[i+1][j-1]是否也是回文子串，在回圈的程序中不斷更新最大回文子串的長度，注意子串的長度是0或1也算回文子串
復雜度：時間復雜度O(n^2)，兩層回圈，空間復雜度O(n^2)，即動態規劃dp陣列的空間，
由于單個字符它一定是回文字串也就是i等于j的時候，由于dp[i][j]代表的是[i,j]是否有回文字串所以i是要小于j的所以只需要填對角線下方的空格所以i的范圍是[0,len-2],j的范圍是[1,len-1]
對應代碼：
class Solution { public: string longestPalindrome(string s) { int len=s.size(); if(len<=1)return s; bool dp[1001][1001]={false}; for(int i=0;i<len;i++){ dp[i][i]=true;//單個字母一定是true; } int start=0; int maxlen=1; for(int j=1;j<len;j++){ for(int i=0;i<len-1&&i<j;i++){ if(s[i]!=s[j]){ dp[i][j]=false;//不是回文串 } else{ if(j-i<3){//這種情況必然為true; dp[i][j]=true; } else{ dp[i][j]=dp[i+1][j-1];//狀態轉移方程 } } if(dp[i][j]&&j-i+1>maxlen){//獲取最長的回文字串 maxlen=j-i+1; start=i; } } } return s.substr(start,maxlen); } };
下面博主來解釋一個為什么j-i<3他必然是true;
2.驗證回文串
對應letecode鏈接：力扣
題目描述：
給定一個字串，驗證它是否是回文串，只考慮字母和數字字符，可以忽略字母的大小寫，
說明：本題中，我們將空字串定義為有效的回文串，
示例 1:
輸入: "A man, a plan, a canal: Panama"
輸出: true
解釋："amanaplanacanalpanama" 是回文串
示例 2:輸入: "race a car"
輸出: false
解釋："raceacar" 不是回文串提示：
1 <= s.length <= 2 * 105
字串 s 由 ASCII 字符組成
解題思路：
我們可以定義一個string 把所有的字母全都放進去并且全部將其變成小寫，在將其翻轉，在和遍歷得到的字串比較是否相等
對應代碼：
class Solution { public: bool isPalindrome(string s) { string t; for(auto tmp:s) { if(isalnum(tmp))//判斷是否是字母 { t+=tolower(tmp); } } string w(t.rbegin(),t.rend()); return w==t; } };
方法二：雙指標
們直接在原字串 s 上使用雙指標，在移動任意一個指標時，需要不斷地向另一指標的方向移動，直到遇到一個字母或數字字符，或者兩指標重合為止，也就是說，我們每次將指標移到下一個字母字符或數字字符，再判斷這兩個指標指向的字符是否相同，
對應代碼：
class Solution { public: bool isPalindrome(string s) { int left=0; int right=s.size()-1; while(left<right){ while(left<right&&!isalnum(s[left])) left++;//從左往右找字符 while(left<right&&!isalnum(s[right]))right--;//從右往左找字母 if(left<right){//如果沒有錯開就判斷 if(tolower(s[left])!=tolower(s[right]))return false;//全部轉換成小寫 } left++; right--; } return true; } };
驗證回文串II
對應letecode鏈接：
力扣
題目描述：
給定一個非空字串 s，最多洗掉一個字符，判斷是否能成為回文字串，
示例 1:
輸入: s = "aba"
輸出: true
示例 2:輸入: s = "abca"
輸出: true
解釋: 你可以洗掉c字符，
示例 3:輸入: s = "abc"
輸出: false提示:
1 <= s.length <= 105
s 由小寫英文字母組成
解題思路：
首先判斷原串是否是回文串，如果是，就回傳 \text{true}true；如果不是，則列舉每一個位置作為被洗掉的位置，再判斷剩下的字串是否是回文串，這種做法的漸進時間復雜度是 O(n^2)O(n
2
) 的，會超出時間限制，我們換一種想法，首先考慮如果不允許洗掉字符，如何判斷一個字串是否是回文串，常見的做法是使用雙指標，定義左右指標，初始時分別指向字串的第一個字符和最后一個字符，每次判斷左右指標指向的字符是否相同，如果不相同，則不是回文串；如果相同，則將左右指標都往中間移動一位，直到左右指標相遇，則字串是回文串，
在允許最多洗掉一個字符的情況下，同樣可以使用雙指標，通過貪心實作，初始化兩個指標 low 和 high 分別指向字串的第一個字符和最后一個字符，每次判斷兩個指標指向的字符是否相同，如果相同，則更新指標，將 low 加 1,high 減 1，然后判斷更新后的指標范圍內的子串是否是回文字串，如果兩個指標指向的字符不同，則兩個字符中必須有一個被洗掉，此時我們就分成兩種情況：即洗掉左指標對應的字符，留下子串 s[low+1:high]，或者洗掉右指標對應的字符，留下子串 s[low:high?1]，當這兩個子串中至少有一個是回文串時，就說明原始字串洗掉一個字符之后就以成為回文串
對應代碼：
class Solution { public: bool validPalindrome(string s) { int low=0; int high=s.size()-1; while(low<high){ if(s[low]==s[high]){ low++; high--; } else{ return ispalindrome(s,low+1,high)||ispalindrome(s,low,high-1);//給他一次機會看是否能是回文 } } return true; } bool ispalindrome(string&s,int left,int right){ while(left<right){ if(s[left]!=s[right]){//不是回文回傳false; return false; } left++; right--; } return true; } };
2.考慮最多可以洗掉k個：
實際上這個作為面試題還算比較水的，可能面試官以這題為基礎要求你最多刪k個的情況下，判斷是否能修改字串為回文串，因此我決定寫一下如何處理k個的情況，實際上，這種題目字串題目很容易歸類為動態規劃問題，我們可以把這題轉述為：將字串s處理為字串t，在不能進行替換的情況下最少需要進行多少次操作，然后判斷操作次數是否在允許范圍內
這題就轉換為從字串s轉換為字串t所需要的最小次數：
dp[i][j], 代表s[:i-1] == t[:j-1]所需要的編輯次數
dp[i][j],代表s[:i?1]==t[:j?1]所需要的編輯次數?那么這題就變成了一個很經典的動態規劃問題
dp[i][j]={ dp[i?1][j?1]
min(dp[i][j],dp[i?1][j]+1],dp[i][j?1]+1)
if(s[i?1]==t[j?1])
與上者并不是if,else關系其中當
s[i - 1] == t[j - 1]時，我們只需要看s[:i-2]s[:i?2]和t[:j-2]t[:j?2]的匹配情況
class Solution { public: bool k_validPalindrome(string s, int k){ int n = s.size(); vector<vector<int>> dp(2, vector<int>(n + 1, 0x3f3f3f3f)); // 只需要用前后兩行就好，0x3f3f3f3f擬定的無窮大，足夠大也不容易溢位 for (int i = 0; i <= n; ++ i) dp[0][i] = i; // 初始化,顯然將t[:i-1]修改為空串需要i次操作 for (int i = 1; i <= n; ++ i){ dp[i & 1][0] = i; // 類似上述的初始化，只是在這里才賦值 int from = max(1, i - k), to = min(n, i + k); // k是可以修改的次數,我們可以往前或者往后修改 for (int j = from; j <= to; ++ j){ if (s[i - 1] == s[n - j]) dp[i & 1][j] = dp[(i - 1) & 1][j - 1]; // 參看圖中i = c, j = c dp[i & 1][j] = min({dp[i & 1][j], dp[(i - 1) & 1][j] + 1, dp[i & 1][j - 1] + 1}); // 從i - 1處和j - 1處轉移 } } return dp[n & 1][n] <= 2 * k; // 對原字串的一次修改，反映在兩個字串上是兩次，為了讓s, t相同洗掉k代表可以對每個操作k次,共2*k } bool validPalindrome(string s) { return k_validPalindrome(s, 1); } };
回文字串
對應letcode鏈接：
https://leetcode-cn.com/problems/palindromic-substrings/
題目描述：
給你一個字串 s ，請你統計并回傳這個字串中 回文子串 的數目，
回文字串 是正著讀和倒過來讀一樣的字串，
子字串 是字串中的由連續字符組成的一個序列，
具有不同開始位置或結束位置的子串，即使是由相同的字符組成，也會被視作不同的子串，
示例 1：
輸入：s = "abc"
輸出：3
解釋：三個回文子串: "a", "b", "c"
示例 2：輸入：s = "aaa"
輸出：6
解釋：6個回文子串: "a", "a", "a", "aa", "aa", "aaa"提示：
1 <= s.length <= 1000
s 由小寫英文字母組成
接題思路：
利用回文串的性質找對稱中心由于上面已經講過了在這里就不重復了
對應代碼：
class Solution { public: int ans=0;//記錄結果 int countSubstrings(string s) { int len=s.size(); for(int i=0;i<s.length();i++) { Countpalindrome(i,i,len,s);//長度為奇數 Countpalindrome(i,i+1,len,s);//長度為偶數 } return ans; } void Countpalindrome(int start,int end,int len,string &s) { while(start>=0&&end<len&&s[start]==s[end]) { ans++; start--; end++; } } };
🙌🙌🙌🙌
結語：對于個人來講，在leetcode上進行探索以及單人闖關是一件有趣的時間，一個程式員，如果不喜歡編程，那么可能就失去了這份職業的樂趣，刷到我的文章的人，我希望你們可以駐足一小會，忙里偷閑的閱讀一下我的文章，可能文章的內容對你來說很簡單，(^▽^)不過文章中的每一個字都是我認真專注的見證！希望您看完之后，若是能幫到您，勞煩請您簡單動動手指鼓勵我，我必回報更大的付出~
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/377153.html
標籤：其他
上一篇：演算法學習：動態規劃