[LeetCode] 接下來要比較誰? 用簡單的方式解 #5 Longest Palindromic Substring
LeetCode #5 有各式各樣的解法，可是每一個解法我都不喜歡，暴力破解太慢、DP 解太複雜、中心擴展解基本上跟暴力破解差不多。Manacher's Algorithm 其實不難但是大家都解釋的有點複雜。
所以我今天就來用一個我覺得相對簡單又比暴力破解聰明的做法。
下一個字元有辦法讓前面的回文更長嗎?
其實標題就解釋完了，如果我們從程式的角度思考，我們當然希望從左往右掃過一次全部的字元就應該有解答，寫程式也比較好寫。
首先假設我們掃到一半，發現目前的字元和上一個字元一樣，那這樣當然就是回文:
到下一個 for loop 的時候我們當然希望這個回文可以越來越長，所以我們就把接下來要比較的位置記住。
為什麼不記中間的 index 或目前回文的長度? 也是可以啊，可是這樣最後還是要算最左邊要跟哪個字元比較，還不如直接記住接下來要比較的字元位置比較簡單。
如果回文可以變更長...
看到回文變長，我們當然希望他再更長一點，我們就是很貪心，這時候我們把剛剛比較的位置往左移一格，把新的位置記住，給接下來的 for loop 繼續弄長:
如果回文沒辦法變長了...
那我們就要接受事實，這個回文最多就這麼長了，不可能更長:
所以我們就不用記任何位置了。
如果第一步就失敗...
那也不用做任何事，因為接下來繼續往左右各自拉長也不可能變回文:
另外一種要考慮的回文
中間的 "b" 在這個回文中就不重要，隨便換成其他字元整個綠框中也還是回文:
接下來的 for loop 流程和前面一樣，可以更長就記住位置繼續努力，不能變長就算了。
資料結構的選擇
值得注意的是回文裡面可能有比較短的回文，就像 "夢中夢中夢" 裡面還有一個小的 "夢中夢"，裡面還有更小的 "夢" (一個字元也是回文喔)。
所以要記住的位置可能會越來越多，我們就可以用長度不固定的資料結構來存位置，像是 vector:
當然上面這個狀況要有回文不是 "d" 就是 "b"，所以最多只有一個回文可以有機會變得更長，一定會有一個回文在這陣亡。
Index 超出範圍怎辦?
我們一樣可以和以前文章的技巧一樣，遇到 index 不合法的狀況下就讓他拿到 "\0" 的字元，讓回文碰到他就像撞牆一樣:
來寫程式吧
看完 design spec 到這邊我們心中應該就已經有一版的解法了，我們也不一定要用 C++ 來解，只是剛好這篇的主題是 C++ 所以我才用 C++ 來寫:
#include <vector>
class Solution {
public:
std::string longestPalindrome(std::string s) {
std::vector<int> compareList;
for (int index = 0; index < (int)s.size(); index++) {
const char c = getChar(s, index);
std::vector<int> newCompareList;
// Check if the single character palindrome is longer
checkLongerPalindrome(s, index, index);
// Check previous positions
for (const int compareIndex : compareList) {
if (c == getChar(s, compareIndex)) {
checkLongerPalindrome(s, compareIndex, index);
newCompareList.push_back(compareIndex - 1);
}
}
// Check i-1 position
// For example: aa
// ^ index
if (c == getChar(s, index - 1)) {
checkLongerPalindrome(s, index - 1, index);
newCompareList.push_back(index - 2);
}
// Check i-2 position
// For example: aba
// ^ index
if (c == getChar(s, index - 2)) {
checkLongerPalindrome(s, index - 2, index);
newCompareList.push_back(index - 3);
}
compareList = newCompareList;
}
return m_longestPalindrome;
}
private:
char getChar(const std::string &s, const int pos) {
if (pos < 0 || pos >= (int)s.size()) return '\0';
return s.at(pos);
}
void checkLongerPalindrome(const std::string &s, const int startPos,
const int endPos) {
const int length = endPos - startPos + 1;
if (length > (int)m_longestPalindrome.size()) {
m_longestPalindrome = s.substr(startPos, length);
}
}
private:
std::string m_longestPalindrome = "";
};
checkLongerPalindrome 會檢查目前看的回文是不是更長，更長就存起來。只不過我們連一個字元的回文也要檢查是不是有點蠢? 其實是可以把 s 第一個字元當作是最短的回文先設成 output，不過程式碼越多例外狀況處理就越容易有 bug，所以任何回文都給我跑一次 checkLongerPalindrome!
結果
基本上這解法還是 O(n^2) 不過至少我覺得比其他 O(n^2) 解法要聰明一點，而且也比較原創。記憶體空間其實可以更省，因為我們用 vector 所以記憶體會花的比別人多一點:
GitHub
下一篇我用對稱圖片來講解 Manacher's Algorithm，今天就先這樣啦。
留言
發佈留言