回文串是一個正著讀和反著讀順序一樣的字符串。aba 是回文串a(chǎn)bba 是回文串a(chǎn)bc 不是回文串?；匚拇念}目都要使用一個基本的邏輯就是判斷當(dāng)前這個字符串是不是回文串。以 c 為例代碼如下。這種方法也可以稱為雙指針法兩個指針從字符串的兩端向中間遍歷每個字符如果中間發(fā)現(xiàn)兩個字符不相同則不是回文字符串遍歷到最后說明是回文串。bool isPalindrome(const string s) { int len s.size(); if (len 1) { return true; } int left 0; int right len - 1; //決策使用還是就看有沒有必要在這里沒有必要所以使用 while (left right) { if (s[left] ! s[right]) { return false; } left; right--; } return true; }雙指針法在其它數(shù)據(jù)結(jié)構(gòu)題目中也會用到比如鏈表中會用到快慢指針也屬于雙指針?？焖倥判蛩惴ㄖ薪o選中的數(shù)據(jù)找到合適的位置也會使用兩個指針從兩邊向中間對數(shù)據(jù)進行遍歷也屬于雙指針。判斷回文串也可以使用從中間向兩邊的方法使用這種方法時首先需要判斷字符串的長度是奇數(shù)還是偶數(shù)如果是奇數(shù)的話那么兩個指針從中間的位置開始向兩邊遍歷偶數(shù)的話兩個指針分別從中間兩個元素的位置開始遍歷。沒有特殊要求的話優(yōu)先選用從兩邊向中間的方式來判斷一個字符串是不是回文串。1 驗證回文串leetcode驗證回文串題目要求判斷給定的字符串是不是回文串如果是回文串則返回 true如果原字符串不是回文串那么最多可以刪除一個字符如果刪除一個字符之后的字符串是回文串那么返回 true否則返回 false。1.1 基礎(chǔ)算法1判斷原字符串是不是回文串是回文串返回 true否則執(zhí)行第 2 步2遍歷字符串的每個字符分別將每個字符刪除判斷刪除字符之后的字符串是不是回文串。如果是回文串則返回 true停止遍歷如果字符遍歷結(jié)束則返回 false。這種算法的時間復(fù)雜度是 O(n 的平方)偏大所以優(yōu)先選用第二種方法第二種算法的時間復(fù)雜度是 O(n)。1.2 雙指針動態(tài)判斷1使用雙指針從兩邊向中間遍歷每個字符2如果遍歷到兩個字符不相等則討論如下兩種情況① 刪除左邊的字符判斷子串是不是回文串是的話則返回 true② 刪除右邊的字符判斷子串是不是回文串是的話返回 true如果兩種情況都不是回文串那么返回 false。3如果字符串遍歷結(jié)束都滿足回文串的要求則返回 trueclass Solution { public: bool validPalindrome(string s) { int len s.size(); int left 0; int right len - 1; bool result true; while (left right) { if (s[left] ! s[right]) { if (isPalindrome(s.substr(left 1, right - left))) { return true; } if (isPalindrome(s.substr(left, right - left))) { return true; } return false; } left; right--; } return true; } bool isPalindrome(const string s) { int len s.size(); if (len 1) { return true; } int left 0; int right len - 1; while (left right) { if (s[left] ! s[right]) { return false; } left; right--; } return true; } };2 最長回文子串leetcode最長回文子串一個字符串 s找到 s 中最長的回文子串。2.1 動態(tài)規(guī)劃將所有的子串的情況都遍歷到在遍歷的過程中判斷子串是不是回文串如果是回文串并且長度比已有的回文串長的話那么就更新結(jié)果。屬于動態(tài)規(guī)劃算法。這個算法的事件復(fù)雜度是 O(n 的平方)時間復(fù)雜度較高在 leetcode 上運行時會超時。class Solution { public: string longestPalindrome(string s) { int size s.size(); for (int i 0; i size; i) { for (int j i; j size; j) { if (isPalindrome(s.substr(i, j - i 1))) { if (j - i 1 max_length) { max_length j - i 1; max_str s.substr(i, j - i 1); } } } } return max_str; } private: bool isPalindrome(string s) { int size s.size(); int i 0; int j size - 1; while (i j) { if (s[i] ! s[j]) { return false; } i; j--; } return true; } private: int max_length 0; string max_str; };這個題目要找的是最長回文子串我們能想到 j 的遍歷從大向小遍歷。這樣遍歷的話就是先遍歷長度大的字符串再遍歷長度小的字符串。當(dāng)?shù)谝粋€遍歷到一個字符串是回文串那么這個回文串就是長度最大的回文串就可以直接返回。從小向大進行遍歷當(dāng)遍歷到這個字符串是回文串的時候仍然不能返回因為不能確定這個字符串是不是長度最大的回文串需要將所有情況都遍歷完畢才能確定最大的回文字符串。再進一步思考我們可以以子串的長度作為遍歷的依據(jù)長度從大到小進行遍歷。如下是使用c語言實現(xiàn)的算法。char ret[1001] {\0}; char* longestPalindrome(char* s) { int length strlen(s); if (length 1) { return s; } memset(ret, 0, 1001); for (int len length; len 1; len--) { for (int i 0; i length; i) { if (i len - 1 length) { break; } int start_index i; int end_index i len - 1; if (isPalindrome(s, start_index, end_index)) { int index 0; for (int i start_index; i end_index; i) { ret[index] s[i]; index; } return ret; } } } return NULL; } int isPalindrome(char *s, int start_index, int end_index) { while (start_index end_index) { if (s[start_index] ! s[end_index]) { return 0; } start_index; end_index--; } return 1; }官方題解中也是遍歷了子串的長度但是是從小到大進行遍歷的同時還記錄了已經(jīng)遍歷過的子串的結(jié)果。當(dāng)判斷長度較大的字符串是不是回文串時可以直接基于歷史記錄來做判斷。這也是動態(tài)規(guī)劃常用的思路就是在遍歷的過程中記錄歷史信息這樣在后邊的遍歷中可以直接使用已經(jīng)記錄的歷史信息。官方題解中正因為長度是從小到大進行遍歷的所以在遍歷的時候判斷字符串是不是回文串的時候可以使用歷史信息進行判斷。因為 s[i][j] 比 s[i 1][j - 1] 的長度要大后者是不是回文串已經(jīng)是確定的。2.2 中心擴展法leetcode 官方題解中提供了另外一種方法中心擴展法。這個問題的多種算法之間的區(qū)別就是遍歷的對象不一樣1兩級遍歷遍歷字符串的索引2兩級遍歷一級遍歷子串的長度一級遍歷字符串的索引3中心擴展法也是遍歷字符串的索引不過在計算邏輯上是把索引當(dāng)成了要遍歷的子串的中心class Solution { public: string longestPalindrome(string s) { int size s.size(); int start 0; int end 0; for (int i 0; i size; i) { int left1 i; int right1 i; int left2 i; int right2 i 1; // 從中心向兩邊擴展要考慮兩種情況 // 奇數(shù)的情況偶數(shù)的情況 centerExpand(s, left1, right1); centerExpand(s, left2, right2); 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); } void centerExpand(string s, int left, int right) { while (left 0 right s.size() s[left] s[right]) { left--; right; } // 循環(huán)退出說明最后一個索引不滿足回文串的情況 // 要么是 left 和 right 越界了要么是當(dāng)前這兩個字符不相等 // 這兩種情況下left 需要 , right 需要 -- left; right--; } };3 分割回文子串leetcode分割回文子串本文用基礎(chǔ)的算法去思考的話很難思考下去遇到這種情況一般要考是不是可以使用遞歸算法。第一個想出這種解法的人絕對值得敬佩。class Solution { public: vectorvectorstring partition(string s) { partitionHelper(s, 0); return result_; } void partitionHelper(const string s, int start_index) { int len s.size(); if (start_index len) { result_.push_back(one_instance_); return; } for (int i start_index; i len; i) { if (isPalindome(s, start_index, i)) { one_instance_.push_back(s.substr(start_index, i - start_index 1)); partitionHelper(s, i 1); one_instance_.pop_back(); } } } bool isPalindome(const string s, int start, int end) { if (start end) { return true; } if (flag[start][end] 1) { return true; } if (flag[start][end] -1) { return false; } int tmp_start start; int tmp_end end; while (tmp_start tmp_end) { if (s[tmp_start] ! s[tmp_end]) { flag[tmp_start][tmp_end] -1; flag[start][end] -1; return false; } tmp_start; tmp_end--; } flag[start][end] 1; return true; } private: int flag[20][20] {0}; vectorvectorstring result_; vectorstring one_instance_; };