【Leetcode解題】242. Valid Anagram

題目

• 題目連結
• 目標函式 : isAnagram(s, t)
  • Input : s: str、t: str
  • Output : bool

解題概念

• 題意 : 給予兩個字串 s、t，判斷 s 是否為 t 的 Anagram
• Anagram (同字母異序字) : https://en.wikipedia.org/wiki/Anagram

我的寫法

• 想法 : 使用 Hashmap 去處理
  1. 將 s 與 t 分別轉換為 {字元 : 字元個數} 的 Hashmap
  2. 比較兩個 Hashmap 是否相等
• 程式碼 :

  def string2Hashmap(self, s): # 將字串轉為 Hashmap
      res = dict()
      for c in s:
          if c in res:
              res[c] += 1
          else: # not c in s
              res[c] = 1
      return res
  
  def isAnagram(self, s, t):
      
      if self.string2Hashmap(s) == self.string2Hashmap(t):
          return True
      else:
          return False

• 成效 :
  • Time Complexity : $\color{DB4D6D}{O(n)}$
  • Runtime: 33 ms (faster than 86.67%)
  • Memory Usage: 13.6 MB (more than 99.63%)

解答 or 其他優秀寫法 - Part1

• 想法 : 基本上與我的想法相同，但只使用一個字典
• 程式碼 :

  def isAnagram(self, s, t):
      dic1, dic2 = {}, {}
      for item in s:
          dic1[item] = dic1.get(item, 0) + 1
      for item in t:
          dic2[item] = dic2.get(item, 0) + 1
      return dic1 == dic2

• 成效 :
  • Time Complexity : $\color{DB4D6D}{O(n)}$
  • Runtime: 32 ms (faster than 88.1%)
  • Memory Usage: 13.7 MB (more than 94.86%)

解答 or 其他優秀寫法 - Part2

• 想法 : 直接對兩串進行排序後再比較
• 程式碼 :

  def isAnagram(self, s, t):
      return sorted(s) == sorted(t)

• 成效 :
  • Time Complexity : $\color{DB4D6D}{O(n)}$
  • Runtime: 54 ms (faster than 28.8%)
  • Memory Usage: 14.4 MB (more than 59.22%)