LeetCode #383 Ransom Note 勒索信 – 解題思路分享

Klook.com
文章觀看次數: 425

LeetCode題目翻譯

英文原文如下

Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.

Each letter in magazine can only be used once in ransomNote.

中文翻譯

給予兩個字串 ransomNote 和 magazine，判斷是否可以使用 magazine 中的字母組成 ransomNote。若可以組成，則返回 true，否則返回 false。

magazine 中的每個字母只能在 ransomNote 中使用一次。

範例及題目限制

需要注意的是 ransomNote 和 magazine 都僅有英文小寫

解題思路

這題其實蠻有趣的哈哈!

講到的是看那種老派搶銀行電影都會有的片段，從雜誌上剪字母來組成勒索信

C# 解決方案

方案1 – 兩個Dictionary

public class Solution {
    public bool CanConstruct(string ransomNote, string magazine) {
        Dictionary<char, int> dictR = new Dictionary<char, int>();
        Dictionary<char, int> dictM = new Dictionary<char, int>();

        int num;

        foreach(char i in ransomNote)
        {
            if (!dictR.TryGetValue(i,out num))
            {
                dictR.Add(i, 1);
            }
            else
            {
                dictR[i] = dictR[i]+1;
            }
        }

        foreach(char i in magazine)
        {
            if (!dictM.TryGetValue(i,out num))
            {
                dictM.Add(i, 1);
            }
            else
            {
                dictM[i] = dictM[i]+1;
            }
        }

        foreach(var item in dictR)
        {
            if (!dictM.TryGetValue(item.Key,out num) || dictM[item.Key]<item.Value)
            {
                return false;
            }
        }

        return true;
    }

}

第一個解法中用到了兩個Dictionary，分別將兩個字串以字典的方式儲存

然後最後再針對 dictR 也就是 勒索信的部分進行遞迴判斷

要是dictM (雜誌) 沒有此index或是字數不夠就會回傳 false

方案2 – 一個Dictionary

public class Solution {
    public bool CanConstruct(string ransomNote, string magazine) {
        Dictionary<char, int> dictM = new Dictionary<char, int>();

        int num;

        foreach(char i in magazine)
        {
            if (!dictM.TryGetValue(i,out num))
            {
                dictM.Add(i, 1);
            }
            else
            {
                dictM[i] = dictM[i]+1;
            }
        }

        foreach(char i in ransomNote)
        {
            if (!dictM.TryGetValue(i,out num))
            {
                return false;
            }
            else
            {
                num = dictM[i]-1;
                if(num < 0)
                {
                    return false;
                }
                dictM[i] = num;
            }
        }

        return true;
    }

}

我們當然也可以使用一個字典來儲存就好
在這裡我們把 magazine 的字都儲存進字典，然後逐一確認勒索信要的單字

Java 解決方案

方案1 – 兩個Map

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        Map<Character, Integer> mapR = new HashMap<Character, Integer>();
        Map<Character, Integer> mapM = new HashMap<Character, Integer>();

        for (char r: ransomNote.toCharArray()) {
            if(mapR.containsKey(r))     
            {
                mapR.put(r, mapR.get(r)+1);   
            }
            else
            {
                mapR.put(r, 1);    
            }
        }


        for (char m: magazine.toCharArray()) {
            if(mapM.containsKey(m))     
            {
                mapM.put(m, mapM.get(m)+1);   
            }
            else
            {
                mapM.put(m, 1);    
            }
        }

        for(Map.Entry<Character, Integer> entry : mapR.entrySet()) {
            if(!mapM.containsKey(entry.getKey()))
            {
                return false;
            }

            if(mapM.get(entry.getKey())<entry.getValue())
            {
                return false;
            }
        }

        return true;
    }
}

⭐方案2 – 一個Map

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        Map<Character, Integer> mapM = new HashMap<Character, Integer>();

        for (char m: magazine.toCharArray()) {
            if(mapM.containsKey(m))     
            {
                mapM.put(m, mapM.get(m)+1);   
            }
            else
            {
                mapM.put(m, 1);    
            }
        }

        int num;
        for (char r: ransomNote.toCharArray()) {
            if(mapM.containsKey(r))     
            {
                num = mapM.get(r)-1;
                if(num < 0)
                {
                    return false;
                }
                mapM.put(r, num);   
            }
            else
            {
                return false;  
            }
        }

        return true;
    }
}

Python3 解決方案

方案1

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        dictR = {}
        dictM = {}

        for r in ransomNote:
            if(r in dictR):
                dictR[r] = dictR[r]+1
            else:
                dictR[r] = 1

        for m in magazine:
            if(m in dictM):
                dictM[m] = dictM[m]+1
            else:
                dictM[m] = 1

        for k, v in dictR.items():
            if(k not in dictM):
                return False
            
            if(dictM[k]<v):
                return False

        return True

方案2

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        dictM = {}

        for m in magazine:
            if(m in dictM):
                dictM[m] = dictM[m]+1
            else:
                dictM[m] = 1

        for r in ransomNote:
            if(r in dictM):
                num = dictM[r]-1
                if(num < 0):
                    return False
                dictM[r] = num
            else:
                return False

        return True

JavaScript 解決方案 

/**
 * @param {string} ransomNote
 * @param {string} magazine
 * @return {boolean}
 */
var canConstruct = function(ransomNote, magazine) {
    var dictM = {}

    for (let i = 0; i < magazine.length; i++) {
        var m = magazine[i];
        if(!(m in dictM))
        {
            dictM[m] = 1;
        }
        else
        {
            dictM[m] = dictM[m]+1;
        }
    }

    for (let i = 0; i < ransomNote.length; i++) {
        var r = ransomNote[i];
        if(!(r in dictM))
        {
            return false;
        }
        else
        {
            var num = dictM[r]-1;

            if(num < 0)
            {
                return false;
            }

            dictM[r] = num;
        }
    }
    return true;
};

結論

寄勒索信是件不好的事情，大家切記不要寫不出來解答就去勒索別人! !

“喔 原來你勒索我!”

— 電影【功夫】 醬爆

🧡如果這篇文章有幫上你的一點點忙，那是我的榮幸

🧡幫我分享或是收藏，我都會很感激的

✅如有任何疑問，歡迎透過留言或messenger讓我知道 !

題目連結 : Ransom Note – LeetCode

隨機文章

相關文章

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *