每日一道 LeetCode (48):最長(zhǎng)回文子串
?每天 3 分鐘，走上算法的逆襲之路。
?
前文合集
代碼倉(cāng)庫
GitHub：https://github.com/meteor1993/LeetCode
Gitee：https://gitee.com/inwsy/LeetCode
題目：最長(zhǎng)回文子串
難度：「中等」
題目來源：https://leetcode-cn.com/problems/longest-palindromic-substring/
給定一個(gè)字符串 s，找到 s 中最長(zhǎng)的回文子串。你可以假設(shè) s 的最大長(zhǎng)度為 1000。
示例 1：
輸入:?"babad"
輸出:?"bab"
注意:?"aba"?也是一個(gè)有效答案。
示例 2：
輸入:?"cbbd"
輸出:?"bb"
解題方案一：暴力解法
暴力方案就很適合我這種腦子不夠用的人，首先把字符串中的所有子串取出來，當(dāng)然哈，取長(zhǎng)度大于 1 的子串，不然也沒啥意義。
然后挨個(gè)判斷取出來的子串是否回文串，判斷完了以后取到最大的那個(gè)，然后返回出來，結(jié)束。
public?String?longestPalindrome(String?s)?{
????int?len?=?s.length();
????if?(len?2)?{
????????return?s;
????}
????//?先把字符串轉(zhuǎn)成數(shù)組
????char[]?charArray?=?s.toCharArray();
????//?定義初始位置
????int?left?=?0;
????//?定義字符串長(zhǎng)度
????int?length?=?1;
????//?獲取所有子串
????for?(int?i?=?0;?i?1;?i++)?{
????????for?(int?j?=?i?+?1;?j?????????????if?(j?-?i?+?1?>?length?&&?valid(charArray,?i,?j))?{
????????????????left?=?i;
????????????????length?=?j?-?i?+?1;
????????????}
????????}
????}
????return?s.substring(left,?left?+?length);
}
//?判斷是否回文串
private?boolean?valid(char[]?charArray,?int?left,?int?right)?{
????while?(left?????????if?(charArray[left]?!=?charArray[right])?{
????????????return?false;
????????}
????????left++;
????????right--;
????}
????return?true;
}
這個(gè)答案慢肯定是慢，時(shí)間復(fù)雜度達(dá)到了 O(n^3) ，不慢才有鬼了。
解題方案二：中心擴(kuò)散
上面的方案是從兩邊開始往中間夾，中心擴(kuò)散的思想是從中間開始往兩邊進(jìn)行擴(kuò)散。
我在答案中找到了一個(gè)非常形象的圖解，和大家分享一下：
解釋一下這張圖，現(xiàn)在假設(shè)有一個(gè)字符串 「acdbbdaa」 ，從第一個(gè) b 位置開始找最長(zhǎng)回文串。
- 首先往左尋找與當(dāng)期位置相同的字符，直到遇到不相等為止。
- 然后往右尋找與當(dāng)期位置相同的字符，直到遇到不相等為止。
- 最后左右雙向擴(kuò)散，直到左和右不相等。
這時(shí)我們找到了從 b 開始最長(zhǎng)的回文子串，然后在程序中記錄下來。
每一個(gè)位置開始都按這個(gè)方案去找最長(zhǎng)的回文子串，最后得到的結(jié)果就是最長(zhǎng)的回文子串。
public?String?longestPalindrome_1(String?s)?{
????if?(s?==?null?||?s.length()?==?0)?return?"";
????int?length?=?s.length();
????//?定義左右指針
????int?left?=?0,?right?=?0;
????//?定義長(zhǎng)度
????int?len?=?1;
????//?定義最大開始位置和最長(zhǎng)子串長(zhǎng)度
????int?maxStart?=?0,?maxLen?=?0;
????for?(int?i?=?0;?i?????????left?=?i?-?1;
????????right?=?i?+?1;
????????//?計(jì)算左邊
????????while?(left?>=?0?&&?s.charAt(left)?==?s.charAt(i))?{
????????????len++;
????????????left--;
????????}
????????//?計(jì)算右邊
????????while?(right?????????????len++;
????????????right++;
????????}
????????//?兩邊一起擴(kuò)散
????????while?(left?>=?0?&&?right?????????????len?+=?2;
????????????left--;
????????????right++;
????????}
????????//?如果當(dāng)前長(zhǎng)度大于最大長(zhǎng)度
????????if?(len?>?maxLen)?{
????????????maxLen?=?len;
????????????maxStart?=?left;
????????}
????????//?下次循環(huán)前重置?len
????????len?=?1;
????}
????return?s.substring(maxStart?+?1,?maxStart?+?1?+?maxLen);
}
解題方案三：動(dòng)態(tài)規(guī)劃
動(dòng)態(tài)規(guī)劃我的理解實(shí)際上就是一個(gè)把已經(jīng)判斷過的信息緩存起來的一種方案，很像我們?cè)谧?Web 開發(fā)的時(shí)候用到的 redis ，只是在答案中換成了一個(gè)矩陣或者說是二維數(shù)組。
如果一個(gè)字符串 s[l, r] 是一個(gè)回文串，那么 s[l + 1, r - 1] 一定也是一個(gè)回文串，相當(dāng)于兩頭各去掉一個(gè)字符。
如果這時(shí)我們直接通過某種方式直接可以知道 s[l + 1, r - 1] 是一個(gè)回文串，那么只需要判斷 s[i] 和 s[j] 相等就可以了。
所以就有了下面的代碼：
public?String?longestPalindrome_2(String?s)?{
????if?(s?==?null?||?s.length()?==?0)?return?s;
????int?length?=?s.length();
????int?maxStart?=?0;??//最長(zhǎng)回文串的起點(diǎn)
????int?maxEnd?=?0;????//最長(zhǎng)回文串的終點(diǎn)
????int?maxLen?=?1;??//最長(zhǎng)回文串的長(zhǎng)度
????//?定義一個(gè)布爾矩陣
????boolean[][]?dp?=?new?boolean[length][length];
????for?(int?r?=?1;?r?????????for?(int?l?=?0;?l?????????????if?(s.charAt(r)?==?s.charAt(l)?&&?(r?-?l?<=?2?||?dp[l?+?1][r?-?1]?==?true))?{
????????????????dp[l][r]?=?true;
????????????????if?(r?-?l?+?1?>?maxLen)?{
????????????????????maxLen?=?r?-?l?+?1;
????????????????????maxStart?=?l;
????????????????????maxEnd?=?r;
????????????????}
????????????}
????????}
????}
????return?s.substring(maxStart,?maxEnd?+?1);
}
可以看到耗時(shí)也是蠻多的。
答案中還給出了一種叫做 Manacher 算法的方案，原諒我比較菜，屬實(shí)是沒看懂，就不拿出來獻(xiàn)丑了。
