iT邦幫忙

2025 iThome 鐵人賽

DAY 9
0
自我挑戰組

從零開始學習LeetCode系列 第 9

Day9 Valid Anagram

  • 分享至 

  • xImage
  •  

題目:給你兩個字串 s 和 t,判斷它們是不是 字母異位詞 (anagram)。
• 兩字串長度必須相同
• 出現的字母次數必須完全一樣
• 不能只比較字母順序,因為順序可以不同
https://ithelp.ithome.com.tw/upload/images/20250923/20169339aN38RL92kq.jpg


解法一
https://ithelp.ithome.com.tw/upload/images/20250923/20169339odh5hmxBOS.jpg

  • 排序(最直覺)
  • 把兩個字串排序,如果排序後結果一樣,就代表兩個字串的字母組成完全相同
  • 遇到高效能需求時(例如字串長度達到上百萬),排序法就不太合適

註解:

  • sorted(s):會把字串變成一個排序好的列表
    例如 "anagram" → ['a','a','a','g','m','n','r']
  • 只要排序結果一樣,就代表兩個字串的字母組成相同

解法二
https://ithelp.ithome.com.tw/upload/images/20250923/201693397a2972ujOu.jpg

  • HashMap 計數(最常用)
  • 程式碼比排序法稍微冗長
  • 需要額外的記憶體來存放字典

註解:

  • count.get(ch, 0):如果字母沒出現過,預設是 0
  • 第一個迴圈:把 s 每個字母都加進字典
  • 第二個迴圈:再把 t 的字母扣掉,如果發現超出範圍就直接判斷為 False

解法三
https://ithelp.ithome.com.tw/upload/images/20250923/20169339zZeG2yvfha.jpg

  • 本質上等於用 HashMap 計數法,但寫法更精簡
  • 內建 Counter(最精簡)

註解:

  • Counter(s) 會自動幫你算出每個字母出現的次數。
    例如 "anagram" → {'a':3, 'n':1, 'g':1, 'r':1, 'm':1}
  • 直接比較兩個 Counter 是否相等即可。

上一篇
Day8 Contains Duplicate II
下一篇
Day10 Intersection of Two Arrays
系列文
從零開始學習LeetCode11
圖片
  熱門推薦
圖片
{{ item.channelVendor }} | {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言