【LeetCode】005-最長迴文子串

題目

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example:

Input: "cbbd"

Output: "bb"

目前的解法

如最長迴文子串--Manacher 演算法及[轉]最長迴文子串--4種解法 - 立航 - 博客園中所說，有：

1. BF 暴力破解法

2. DP 動態規劃法
3. 中心拓展法
4. Manacher法

那麼Manacher法應該是複雜度最低的，為O(N)。

然而，，我就是要另尋出（si）路，有沒有其他的辦法呢？

大開腦洞

githubwoniu/learnprogram

最簡便的找字元串中最長迴文子串的方法是什麼？ - 知乎

下面是優化思路：

首先，一個迴文串的字元頻度應該是：中點頻度最低為1，其他字元頻度最低為2。

那麼，如果串中有頻度是1的字元，它肯定位於迴文串的中心，不然就不屬於任何迴文串。

因此，按頻度可以篩選掉一定量的多餘字元，將母串進行分割。分割的好處是子串有界。

最懶方法：遍歷整串，從中心向兩側擴張（中心擴散法）並做比較，取得長度，最後返回最大長度所在的串。

優化：

• 在遍歷整串過程中，最大長度maxlen會時刻增加，那麼，當分割後的有界子串長度小於最大長度maxlen時，就不需要再去判斷了。
• 如果串的某個連續子串(len>=2)它們的頻度都是1，那麼它們就不屬於任何迴文串，可以快速剔除，節省時間。這是關鍵。
• 其他方法還沒想到，歡迎補充。

所以大體的思路是：

1. 統計字元頻度，用數組表示頻數
2. 找出頻度為1的字元a，看以a為單核中心向外擴散，求最長迴文；如果沒有迴文，就將它從串中斷開，進行分治；如果迴文長度超過記錄，就保存它
3. 然後從左到右查迴文，只有長度超過記錄，才保存
4. 第一次串分割完畢後，進行分治，重新統計頻度，回到1步驟

新方法評價

目測新方法的複雜度是高於O(N)的，不過，將分治法運用於本題也算是另闢蹊徑了。奇葩方法就是將幾種方法揉合在一起，那麼本方法結合了：

1. 遞歸分治，將頻度為1的字元作為可能的分割點
2. 中心擴散，目前最優值N，那麼從當前點(P)的P-N和P+N進行比較，先N遞減，然後遞增

3. 緩存最優解，當前解N，那麼小於N的情況就忽略了

無論如何，本方法就是不修改原始字元串哈哈~

上代碼

用時6ms https://leetcode.com/submissions/detail/97501094/

class Solution {n int count[256];nnpublic:n string longestPalindrome(string str) {n int start = 0, end = str.length() - 1;n if (longestPalindrome(str.c_str(), start, end) > 1) {//這裡改了下n return str.substr(start, end - start + 1);n } else {n return str.substr(0, end < start ? 0 : 1);n }n }nn int longestPalindromePartition(const char *str, int &start, int &end, int maxLen) {n if (end - start + 1 <= maxLen)n return 1;n int maxStart, maxEnd, len = maxLen;n int reserve = (maxLen + 1) / 2;n int reserveEnd = end - reserve + 1;n for (int i = start + reserve - 1, j, k; i <= reserveEnd; ++i) {n if (str[i] == str[i + 1]) {n for (j = i + 1, k = 1; i - k >= start && j + k <= end; ++k) {n if (str[i - k] != str[j + k])n break;n }n k--;n if (j - i + 1 + k * 2 > len) {n len = j - i + 1 + k * 2;n reserve = (len + 1) / 2;n reserveEnd = end - reserve + 1;n maxStart = i - k;n maxEnd = j + k;n }n }n for (j = reserve; j > 0; --j) {n if (str[i - j] != str[i + j])n break;n }n if (j == 0) {n for (j = reserve + 1; i - j >= start && i + j <= end; ++j) {n if (str[i - j] != str[i + j])n break;n }n reserve = --j;n reserveEnd = end - reserve;n if (j * 2 + 1 > len) {n len = j * 2 + 1;n maxStart = i - j;n maxEnd = i + j;n }n }n }n if (maxLen < len) {n start = maxStart;n end = maxEnd;n return len;n }n return 1;n }nn int longestPalindrome(const char *str, int &start, int &end) {n if (start == end)n return 1;n for (int i = 0; i <= 26; ++i) {n count[a + i] = 0;n }n int len = end - start + 1;n for (int i = start; i <= end; ++i) {n count[str[i]]++;n }n auto dups = new int[len];n int dupCount = 0;n for (int i = start; i <= end; ++i) {n dups[i] = count[str[i]] > 1 ? (dupCount++, 1) : 0;n if (dups[i] == len)n return len;n }n int tmpStart = -1, tmpEnd = -1, maxStart = -1, maxEnd = -1, tmpLen, maxLen = 1;n for (int i = start; i <= end; ++i) {n if (dups[i]) {n tmpStart = i++;n for (; i <= end; ++i) {n if (!dups[i]) {n tmpEnd = i - 1;n break;n }n }n if (i-- > end) {n tmpEnd = end;n }n if ((tmpLen = longestPalindromePartition(str, tmpStart, tmpEnd, maxLen)) > maxLen) {n maxLen = tmpLen;n maxStart = tmpStart;n maxEnd = tmpEnd;n }n } else {n tmpStart = i;n for (; i <= end; ++i) {n if (dups[i]) {n tmpEnd = i - 1;n break;n }n }n if (i-- > end) {n tmpEnd = end;n }n if (tmpStart == tmpEnd) {n while (tmpStart >= start && tmpEnd <= end && str[--tmpStart] == str[++tmpEnd]);n tmpLen = (--tmpEnd) - (++tmpStart) + 1;n if (tmpLen > maxLen) {n maxLen = tmpLen;n maxStart = tmpStart;n maxEnd = tmpEnd;n }n }n }n }n start = maxStart;n end = maxEnd;n delete[]dups;n return maxLen;n }n};n

階段性總結

奇葩方法花了兩天時間去實現，不追求啥，就是好玩。。不去照著實現現有的演算法，也是一種樂趣啊，為什麼一直要走別人的路呢？當自己設計演算法、設計架構、設計界面的時候，才真正是一種創作/創造的過程，才是真正的樂趣所在呢。不過，在這之前，你得首先入門吧~記得好聲音中的一句話，一開始你被音樂玩，後來你才能玩音樂，編程何嘗不是如此呢？

人生三大境界：

1. 搬磚的境界。機械地、條件反射地、枯燥地、重複地勞動，做一件事，為的是把一件小事做熟練、做通透。雖然境界很low，但是有10000小時理論啊，這是不可避免的過程。但是，熟能生巧，在這一境界做出成就後，才能躍升至下一境界。[多維空間某一點]

2. 統籌的境界。能夠把許多件小事安排好，規劃好優先順序，就像知道造一座房子所需的一系列步驟，把它按部就班去完成。懂得取捨，抓住要點，目光不再短淺。許多知識融會貫通，信手拈來。[局部最優點]
3. 設計的境界。同時也是創造的境界。不再拘泥於一扇窗戶、一個房間、一幢房子，全心全意處理的是整體的細節，樹立大局觀，自頂向下處理一件件事。知曉事物的本質，豐富的聯想/舉一反三能力，可以找到兩件不同事之間的相同點，想出獨特的方法。[全局最優點]

推薦閱讀：