iT邦幫忙

2025 iThome 鐵人賽

DAY 27
0
自我挑戰組

從零開始學習LeetCode系列 第 27

Day 27 Longest Common Prefix

  • 分享至 

  • xImage
  •  

題目:給定一個字串陣列 strs,找出其中所有字串的最長共同前綴
如果沒有共同前綴,回傳空字串 ""
https://ithelp.ithome.com.tw/upload/images/20251010/20169339HJszseq3nb.jpg


解法一
https://ithelp.ithome.com.tw/upload/images/20251010/20169339XUDs2elrqt.jpg

  • 水平掃描
  • 取第一個字串作為初始前綴
  • 從第二個字串開始,一個一個比對,縮短前綴直到符合為止
  • 若前綴變成空字串,代表沒有共同前綴

註解

  • prefix = strs[0]:先假設第一個字串是共同前綴
  • s.find(prefix) != 0:檢查 s 是否以 prefix 為開頭
  • prefix = prefix[:-1]:若不是,就縮短 prefix
  • 若 prefix 變成空字串,代表沒有共同前綴

理解

  • 想像你在比三個單字:
    (1)flower
    (2)flow
    (3)flight
  • 一開始 prefix = "flower",
  • 再拿 “flow” 來比對:
    「flower」和「flow」 → 共同部分是 "flow"
  • 再拿 "flight" 來比對:
    「flow」和「flight」 → 共同部分只剩 "fl"
  • 最後答案就是 "fl"
    過程就像慢慢刪掉不一樣的字元,直到剩下最長一樣的開頭

解法二
https://ithelp.ithome.com.tw/upload/images/20251010/201693392QCJBIZ07W.jpg

  • 垂直掃描
  • 取出每一個字母位置 i
  • 檢查所有字串在該位置的字母是否一樣
  • 若不同,就結束回傳結果

理解

  • 逐列比對每個位置的字母

解法三
https://ithelp.ithome.com.tw/upload/images/20251010/20169339pw1RyOOShD.jpg

  • 排序法
  • 先對字串陣列進行排序
  • 只比較第一個字串與最後一個字串
  • 因為排序後,它們的差異最大,前綴也最短

理解

  • 排隊後只比頭尾兩個代表

上一篇
Day 26 Valid Parentheses
系列文
從零開始學習LeetCode27
圖片
  熱門推薦
圖片
{{ item.channelVendor }} | {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言