LeetCode - #125 驗證迴文串

前言

我們社群陸續會將顧毅（Netflix 增長黑客，《iOS 面試之道》作者，ACE 職業健身教練。）的 Swift 演算法題題解整理為文字版以方便大家學習與閱讀。

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

不積跬步，無以至千里；不積小流，無以成江海，Swift社群 伴你前行。如果大家有建議和意見歡迎在文末留言，我們會盡力滿足大家的需求。

難度水平：簡單

1. 描述

給定一個字串，驗證它是否是迴文串，只考慮字母和數字字元，可以忽略字母的大小寫。

說明：本題中，我們將空字串定義為有效的迴文串。

2. 示例

示例 1

輸入: "A man, a plan, a canal: Panama" 輸出: true 解釋："amanaplanacanalpanama" 是迴文串

示例 2

輸入: "race a car" 輸出: false 解釋："raceacar" 不是迴文串

約束條件：

• 1 <= s.length <= 2 * 10^5
• 字串 s 由 ASCII 字元組成

3. 答案

```swift class ValidPalindrome { func isPalindrome(_ s: String) -> Bool { var i = 0, j = s.count - 1 let sChars = Array(s.lowercased())

    while i < j {
        while !sChars[i].isAlphanumeric && i < j {
            i += 1
        }

        while !sChars[j].isAlphanumeric && i < j {
            j -= 1
        }

        if sChars[i] != sChars[j] {
            return false
        } else {
            i += 1
            j -= 1
        }
    }

    return true
}

}

extension Character { var isValid: Bool { return isLetter || isNumber } } ```

• 主要思想：對於 String 前半部分的每個索引，在映象索引處比較兩個值。。
• 時間複雜度： O(n)
• 空間複雜度： O(n)

該演算法題解的倉庫：LeetCode-Swift

點選前往 LeetCode 練習

關於我們

我們是由 Swift 愛好者共同維護，我們會分享以 Swift 實戰、SwiftUI、Swift 基礎為核心的技術內容，也整理收集優秀的學習資料。