LeetCode #383 Ransom Note Solution & Explanation

Post Views: 9

LeetCode Problem

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.

Solution

First solution came out my mind is convert two strings to two dictionaries, English letter as Key and Count as Value.

After converted, we iterate the Dictionary of ransomNote string, and check if any letter was exist or not in the Dictionary of magazine string, if not or count is not enough than return false.

C# Solution

Solution1 – two Dictionaries

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;
    }

}

Solution2 – one Dictionary

In the second solution, we used one dictionary to store and check.

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;
    }

}

Java Solution

Solution1

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;
    }
}

Solution2

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 Solution

Solution1 – two Dictionaries

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

Solution2 – one Dictionary

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 Solution

Solution1

/**
 * @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;
};

Conclusion

🧡If my solution helps, that is my honor!

🧡You can support me by clicking some ad, Thanks a lot

✅If you got any problem about the explanation, please feel free to let me know

The problem link : Ransom Note – LeetCode

Random post

Related Posts

Leave a Reply

Your email address will not be published. Required fields are marked *