Leet 解題練習：Ransom Note

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

題目原文描述 https://leetcode.com/problems/ransom-note/

中文描述

給定兩個字串 ransomNote 與 magazine。判斷 ransomNote 是否可由 magazine 中的英文字母所組成。 magazine 中的每一個英文字母只能使用一次。

範例一：

輸入 ransomNote = "c", magazine = "d"

輸出 false

範例二：

輸入 ransomNote = "bb", magazine = "bc"

輸出 false

範例三：

輸入 ransomNote = "aabc", magazine = "cbaa"

輸出 true

範例四：

輸入 ransomNote = "bb", magazine = "bcb"

輸出 true

解法一：

判斷 ransomNote 的一個字母是否有在 magazine 出現，若沒有輸出 false。

若有，則將此字母從 magazine 移除。

ransomNote 每個字母都判斷完畢後，即可輸出 true。

Python Code

class Solution:

    def canConstruct(self, ransomNote: str, magazine: str) -> bool:

        for ch in ransomNote:

            if ch not in magazine:

                return False

           

            magazine = magazine.replace(ch, '', 1)

        return True

解法二：

使用 key 和 value 的資料結構 letterDic，將 magazine 的每個字母出現的個數統計起來。

判斷 ransomNote 的一個字母是否有在 letterDic 的所有 key 值中出現，若沒有，輸出 false。

若有，將此 key 的 value 減去 1，若此 value 值為零時，從 letterDic 刪除此 key。

ransomNote 每個字母都判斷完畢後，即可輸出 true。

Python Code

class Solution:

    def canConstruct(self, ransomNote: str, magazine: str) -> bool:

        letterDic = {}

        for ch in magazine:

            if ch in letterDic:

                letterDic[ch] = letterDic[ch] + 1

            else:

                letterDic[ch] = 1

       

        for ch in ransomNote:

            if ch not in letterDic:

                return False

           

            letterDic[ch] = letterDic[ch] - 1

            if letterDic[ch] == 0:

                del letterDic[ch]

       

        return True