【leetcode刷題】20.最長回文子串——Java版

前言

哈喽，大家好，我是一條。

糊塗算法，難得糊塗

今天來一道中等題，看看自己功力幾何？

Question

5. 最長回文子串

難度：中等

給你一個字元串 s，找到 s 中最長的回文子串。

示例 1：

輸入：s = "babad"
輸出："bab"
解釋："aba" 同樣是符合題意的答案。      

示例2:

輸入：s = "cbbd"
輸出："bb"      

示例3:

輸入：s = "a"
輸出："a"      

示例4:

輸入：s = "ac"
輸出："a"      

提示：

1 <= s.length <= 1000

s 僅由數字和英文字母（大寫和/或小寫）組成

Solution

之前我們做過一道題是：最長不重複子串。當時使用的是滑動視窗法。

這道題增加了回文的限制，那麼該怎麼處理回文，可以在紙上寫一個回文串觀察一下，有什麼特點呢？

從中心點向兩端發散

對吧，是以我們要滑動這個中心點，并對每一個中心點，進行左右擴充，判斷左右字元是否相等即可。

把null和空字元串的特殊情況處理掉

有一個可滑動且大小可變的視窗，視窗左端（start）不動，右端（end）向後移動

由于字元串長度有奇數和偶數兩種，是以我們需要同時計算從一個字元開始擴充和從兩個字元之間開始擴充

找出兩種擴充中相對長的作為目前最大值

新的start要從何處開始，如何擴充字元串隻需要考慮的問題

還有一種馬拉車算法更加快速，但有一定難度，面試一般不會出現，感興趣的同學可以看一下

Code

所有leetcode代碼已同步至github

歡迎star

/**
 * @author yitiaoIT
 */
class Solution {
    public String longestPalindrome(String s) {
    if (s == null || s.length() < 1) return "";
    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        int len1 = expandAroundCenter(s, i, i);
        int len2 = expandAroundCenter(s, i, i + 1);
        int len = Math.max(len1, len2);
        if (len > end - start) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    return s.substring(start, end + 1);
}

private int expandAroundCenter(String s, int left, int right) {
    int L = left, R = right;
    while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
        L--;
        R++;
    }
    return R - L - 1;
}
      

Result

複雜度分析

• 時間複雜度：O(N)

🌈尋寶

⭐今天是堅持刷題更文的第20/100天

⭐各位的點贊、關注、收藏、評論、訂閱就是一條創作的最大動力

⭐更多算法題歡迎關注專欄《leetcode》

為了回饋各位粉絲，禮尚往來，給大家準備了一條多年積累下來的優質資源，包括 學習視訊、面試資料、珍藏電子書等

怎麼領取請大家自己找，尋寶遊戲現在開始。

找不到可以評論留言，一條就會注意到你。

如果還不行，請私信我。