iT邦幫忙

2023 iThome 鐵人賽

DAY 26
0

破題

本題的目的是檢查一個字串是否為迴文。迴文是指一個字串從前往後讀和從後往前讀是相同的。

跟一流的人才幹大事,享受成功進步的高級樂趣!
內推機會來啦!能與優秀的程式設計師共事,是特別痛快的事,因為厲害的工程師大神會刺激你想要迎頭趕上的上進心,尤其是一起討論解決方案時,他們會觸發你有更好的解決思維能力,彼此共同成長並且一起享受解謎與破關般的樂趣。 你一定聽得懂我在說甚麼感覺,趕快把握機會,動動手指投遞履歷吧! 立即加入「面試讀書會」,和大家一起準備面試!

https://ithelp.ithome.com.tw/upload/images/20230915/20151958nT7kgUzy4M.png 內推機會 https://ithelp.ithome.com.tw/upload/images/20230902/20151958hbhGNE7BJ4.png 加入讀書會 (邀請碼:7713)

解題思路

  1. 我們使用正則表達式 [^A-Za-z0-9] 來移除字串中所有非英文字母和數字的字符。這樣做的目的是讓我們只需要關注字串中的英文字母和數字。
  2. 我們將整個字串轉換為小寫,以便於比較。
  3. 我們使用一個迴圈從字串的兩端開始比較字元。如果在任何時候,兩端的字元不相同,我們就回傳 false。如果迴圈成功地遍歷了整個字串而沒有找到不相同的字元,那麼我們就回傳 true

程式

class Solution {
    fun isPalindrome(s: String): Boolean {
        val regex = Regex("[^A-Za-z0-9]")
        val ans = regex.replace(s, "").toLowerCase()
        
        for (index in 0 until ans.length / 2) {
            if (ans[index] != ans[ans.length - 1 - index]) return false
        }
        return true
    }
}

複雜度分析

  • 時間複雜度:
    On,其中 n 是字串的長度。這是因為我們需要遍歷整個字串來檢查它是否為迴文。

  • 空間複雜度:
    On,因為我們只使用了固定數量的變量,並且不會隨著輸入大小的增加而增加。即使在最壞的情況下,也只需要存儲原始字串和處理過的字串,所以空間複雜度為常數。

pp 更多 LeetCode 解答在此,一起來學習!

內推機會來啦!

跟一流的人才幹大事,享受成功進步的高級樂趣!

https://ithelp.ithome.com.tw/upload/images/20230915/20151958nT7kgUzy4M.png 內推機會 https://ithelp.ithome.com.tw/upload/images/20230902/20151958hbhGNE7BJ4.png 加入讀書會 (邀請碼:7713)

上一篇
LeetCode 210. Course Schedule II
下一篇
LeetCode 236. Lowest Common Ancestor of a Binary Tree
系列文
破解 Android 工程師面試白板題:30 道面試題目與解答30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言