LeetCode – Ransom Note

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.

LeetCode problem 383

Example 1:

Input: ransomNote = "a", magazine = "b"
Output: false

Example 2:

Input: ransomNote = "aa", magazine = "ab"
Output: false

Example 3:

Input: ransomNote = "aa", magazine = "aab"
Output: true

This problem is very straight forward. We have a bunch of letters that we can use to create our ransomNote. One way would be to use a List to store the magazine and check if the character exists in our list, and remove each magazine character after each ransom character. However, that would be bad if we had a lot of character in our list.

If we would use a HashMap, or Dictionary in C#, then we could store how many times the character appear instead.

First of all, we initialize two Dictionaries

    Dictionary<char, int> magazineChars = new Dictionary<char, int>();
    Dictionary<char, int> ransomChars = new Dictionary<char, int>();

Let’s store our characters in each of the Dicitionaries:

    for (int i = 0; i < magazine.Length; i++)
    {
        if (magazineChars.ContainsKey(magazine[i]))
        {
            magazineChars[magazine[i]]++;
        }
        else
        {
            magazineChars.Add(magazine[i], 1);
        }
    }
    for (int i = 0; i < ransomNote.Length; i++)
    {
        if (ransomChars.ContainsKey(ransomNote[i]))
        {
            ransomChars[ransomNote[i]]++;
        }
        else
        {
            ransomChars.Add(ransomNote[i], 1);
        }
    }

Then we proceed to go through the characters which is our Key, from our ransom Dictionary:

        foreach(char c in ransomChars.Keys) {
            if(!magazineChars.ContainsKey(c)) {
                return false;
            }
            if(magazineChars[c] < ransomChars[c]) {
                return false;
            }
        }

What is good here is that we only go through the list of our ransom and do constant lookup and check their values if there is less amount of characters of c as in our magazine Dictionary. If there is less of a character in the magazine Dicitonary than in our ransom, that means we can’t create our ransom note, and the result is therefore false. If we have enough characters, we proceed. Full code below.

public class Solution {
    public bool CanConstruct(string ransomNote, string magazine) {
        Dictionary<char, int> magazineChars = new Dictionary<char, int>();
        Dictionary<char, int> ransomChars = new Dictionary<char, int>();
        
        for(int i = 0; i < magazine.Length; i++) {
            if(magazineChars.ContainsKey(magazine[i])) {
                magazineChars[magazine[i]]++;
            } else {
                magazineChars.Add(magazine[i], 1);
            }
        }

        for(int i = 0; i < ransomNote.Length; i++) {
            if(ransomChars.ContainsKey(ransomNote[i])) {
                ransomChars[ransomNote[i]]++;
            } else {
                ransomChars.Add(ransomNote[i], 1);
            }
        }
        
        foreach(char c in ransomChars.Keys) {
            if(!magazineChars.ContainsKey(c)) {
                return false;
            }
            if(magazineChars[c] < ransomChars[c]) {
                return false;
            }
        }
         
        return true;
    }
}