125. Valid Palindrome

Easy

Description

給定字串 s，判斷它是否為回文。只考慮英數字元，忽略大小寫。空字串視為回文。

Example:

Input: s = “A man, a plan, a canal: Panama” Output: true

Intuition#

核心思路：用左右指針從兩端往中間逼近，跳過非英數字元，逐一比較。

回文的定義是正讀反讀相同，最直覺的做法就是雙指針從兩端比對
需要先過濾非英數字元，有兩種策略：預處理成乾淨字串、或在比較時動態跳過
動態跳過更省空間，不需額外建立新字串

Approaches#

1: 預處理 + 反轉比較#

概念: 先過濾出所有英數字元並轉小寫，再比較原字串與反轉後的字串是否相同
時間複雜度: O(n) - 過濾一次、反轉一次、比較一次
空間複雜度: O(n) - 需要儲存過濾後的字串

class Solution {
    fun isPalindrome(s: String): Boolean {
        val filtered = s.filter { it.isLetterOrDigit() }.lowercase()
        return filtered == filtered.reversed()
    }
}

⭐2: Two Pointers（原地比較）#

概念: 左指針從頭、右指針從尾開始，遇到非英數字元就跳過，兩端字元轉小寫後比較，不等則回傳 false
時間複雜度: O(n) - 每個字元最多被訪問一次
空間複雜度: O(1) - 只用兩個指針變數

class Solution {
    fun isPalindrome(s: String): Boolean {
        var left = 0
        var right = s.length - 1

        while (left < right) {
            while (left < right && !s[left].isLetterOrDigit()) left++
            while (left < right && !s[right].isLetterOrDigit()) right--

            if (s[left].lowercaseChar() != s[right].lowercaseChar()) {
                return false
            }

            left++
            right--
        }

        return true
    }
}

注意內層 while 跳過非英數字元時，必須同時檢查 left < right，否則可能越界。

🔑 Takeaways#

Pattern: 相向雙指針是判斷回文的經典模式
關鍵技巧: 在比較時動態跳過無關字元，避免額外空間；isLetterOrDigit() 和 lowercaseChar() 是 Kotlin 處理字元的實用 API