242. Valid Anagram

發表於 更新於 分類於 ， 閱讀次數： 文章字數： 749

種類 : hash table
難度 : easy
題目 : 242. Valid Anagram

思維邏輯

  1. 建立長度為26的list，並初始化為0
  2. 逐一歷遍s
    1. 使用ord()將字母轉為int
    2. 減去ord('a')將該索引位置+1
  3. 逐一歷遍t
    1. 使用ord()將字母轉為int
    2. 減去ord('a')將該索引位置-1
  4. 檢核list若有不為0，輸出False; 均為0輸出True

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        letter_list = []
        for _ in range(26):
            letter_list.append(0)
        # initialize list
        # letter_list = [0] * 26
        
        for i in s:
            letter_list[ord(i)-ord('a')] += 1
        for i in t:
            letter_list[ord(i)-ord('a')] -= 1
        for _ in letter_list:
            if _ != 0:
                return False
        return True

時間複雜度: O(n)
空間複雜度: O(26) -> O(1)

難點

  1. set與dict無法儲存重複字元，需使用list累加

最佳解法

1
2
3
4
5
6
7
8
# Counter
"""
非最佳解，'Counter': 快速統計每個元素套件
"""
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        from collections import Counter
        return Counter(s) == Counter(t)