[[435871]]

前言

我們社區陸續會將顧毅(Netflix 增長黑客，《iOS 面試之道》作者，ACE 職業健身教練。微博:@故胤道長[1])的 Swift 算法題題解整理為文字版以方便大家學習與閱讀。

LeetCode 算法到目前我們已經更新了 3 期，我們會保持更新時間和進度(周一、周三、周五早上 9:00 發布)，每期的內容不多，我們希望大家可以在上班路上閱讀，長久積累會有很大提升。

不積跬步，無以至千里;不積小流，無以成江海，Swift社區 伴你前行。

難度水平：中等

1. 描述

給定一個字符串 s, 返回 s 中的最長回文子字符串.

2. 示例

示例 1

輸入：s = "babad" 
輸出： "bab" 
解釋： "aba" 同樣是有效答案。 

示例 2

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

示例 3

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

示例 4

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

約束條件：

• 1 <= s.length <= 1000
• s 僅由數字和英文字母組成。

3. 答案

class LongestPalindromicSubstring { 
    func longestPalindrome(_ s: String) -> String { 
        guard s.count > 1 else { 
            return s 
        } 
         
        let sChars = Array(s) 
        var maxLen = 0, start = 0 
         
        for i in 0..<sChars.count { 
            searchPalindrome(sChars, i, i, &start, &maxLen) 
            searchPalindrome(sChars, i, i + 1, &start, &maxLen) 
        } 
         
        return String(sChars[start..<start + maxLen]) 
    } 
     
    private func searchPalindrome(_ chars: [Character], _ l: Int, _ r: Int, _ start: inout Int, _ maxLen: inout Int) { 
        var l = l, r = r 
         
        while l >= 0 && r < chars.count && chars[l] == chars[r] { 
            l -= 1 
            r += 1 
        } 
         
        if maxLen < r - l - 1 { 
            start = l + 1 
            maxLen = r - l - 1 
        } 
    } 
} 

• 主要思想：從中心的每個索引中找到最長的鏡像字符串。
• 時間復雜度：O(n^2)
• 空間復雜度：O(1)

該算法題解的 github 倉庫是：LeetCode-Swift[2]

點擊前往 LeetCode[3] 練習

參考資料

[1]@故胤道長: https://m.weibo.cn/u/1827884772

[2]LeetCode-Swift: https://github.com/soapyigu/LeetCode-Swift

[3]LeetCode: https://leetcode.com/problems/longest-palindromic-substring/