0242. Valid Anagram - chasel2361/leetcode GitHub Wiki

Given two strings s and t , write a function to determine if t is an anagram of s.

Example 1:
Input: s = "anagram", t = "nagaram"
Output: true

Example 2:
Input: s = "rat", t = "car"
Output: false

Note:
You may assume the string contains only lowercase alphabets.
Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?

這題的目標是檢驗給定的兩個 string 是否由同樣的字母組成，這個問題仍然可以利用 Counter 來解決。

先把 s, t 都轉換成 dict 之後，先檢查 t 的 key 值是否存在於 s 中，再利用 dict.pop() 檢查相對應的 value 是否相同。由於 pop 函式會刪除已取出的物件，檢查完 t 之後只要看 s 中是否還有值就可得知 s 中是否有 t 不存在的字母，寫為程式碼如下

from collections import Counter
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        s = Counter(s)
        t = Counter(t)
        for key, value in t.items():
            if key not in s.keys() or value != s.pop(key):
                return False
        if len(s.keys()) > 0:
            return False
        return True

這樣寫的時間複雜度是 O(N)， 空間複雜度為 O(1)

後來研究了一下如果不使用 Counter 要怎麼解，發現其實可以先把 s 丟進 dict 裡，在檢驗 t 是否與 dict 相符即可

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        dic = {}
        for i in s:
            if i not in dic:
                dic[i] = 1
            else:
                dic[i] += 1

        for j in t:
            if j not in dic:
                return False
            else:
                dic[j] -= 1
        
        for value in dic.values():
            if value != 0:
                return False
                
        return True

這樣寫的時間複雜度是 O(N)，空間複雜度也是 O(1)

寫完之後發現 Counter 可以更簡短，因為 dict 可以直接互相比較內含的 key, value 是否相同，這樣只要一行就可以解決

from collections import Counter
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return Counter(s) == Counter(t)