題目

  • 題目連結
  • 目標函式 : canConstruct(ransomNote, magazine)
    • Input : ransomNote: str、magazine: str
    • Output : bool

解題概念

  • 題意 : 給定兩個字串 ransomNote 和 magazine，如果 ransomNote 可以使用 magazine 中的字母去構造則回傳 true，否則回傳 false
  • magazine 中的每個字母只能在 ransomNote 中使用一次

我的寫法

  • 想法 :
    1. 將 ransomNote 和 magazine 轉為 list 的型態
    2. 對 ransomNote 中每個字元做 for loop:
      • 若該字元出現在 magazine 中，則將該字元從 magazine 中刪除
      • 若否，則直接回傳 false
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    def canConstruct(self, ransomNote, magazine):
        
        r = list(ransomNote)
        m = list(magazine)

        for c in r:
            if c not in m:
                return False
            else:
                m.remove(c)
        return True
  • 成效 :
    • Time Complexity : $\color{DB4D6D}{O(n)}$
    • Runtime: 41 ms (faster than 82.62%)
    • Memory Usage: 13.7 MB (more than 29.5%)

解答 or 其他優秀寫法

  • 想法 :
    1. 改使用 26 格的陣列去儲存 magazine 出現字母的各自次數
    2. 再逐一確認 ransomNote 每個字元的出現次數是否合理
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    def canConstruct(self, ransomNote, magazine):
        
        if len(ransomNote) > len(magazine):
            return False

        hashmap = dict()
        for m in magazine:
            if m in hashmap:
                hashmap[m] += 1
            else:
                hashmap[m] = 1
        =
        for r in ransomNote:
            if (not r in hashmap) or (hashmap[r] == 0):
                return False
            else:
                hashmap[r] -= 1

        return True
  • 成效 :
    • Time Complexity : $\color{DB4D6D}{O(n)}$
    • Runtime: 58 ms (faster than 51.7%)
    • Memory Usage: 13.4 MB (more than 82.64%)