Question

LeetCode Link | 383. Ransom Note | Easy

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.

Constrains

  • 1 <= ransomNote.length, magazine.length <= 10^5
  • ransomNote and magazine consist of lowercase English letters.

Examples

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

Solution Approach

Method: Array / Hash Table

Constrains

  • None

This method does not have any limitations.

Concept Explanation

This question is similar with question 242. Valid Anagram. It does not require same same character count in this question but only if the character in rasnsom note is in scope of magazine. Thus, we could use array with hash method, which is similar with question 242.

Why not use map?

In this case, using a map consumes more space than using an array because a map needs to maintain a red-black tree or a hash table, and it also requires hashing functions, which are time-consuming! The difference becomes apparent when dealing with large data volumes. Therefore, arrays are simpler, more direct, and effective!

Since the problem states that there are only lowercase letters, we can adopt a space-for-time hashing strategy. Use an array of length 26 to record the frequency of each letter in the magazine.

Then, use the ransomNote to verify if this array contains all the letters needed for the ransomNote.

Code

  • Time complexity: O(n)
  • Space complexity: O(1)

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function canConstruct(ransomNote: string, magazine: string): boolean {
    // Base hash
    const pivot: number = 'a'.charCodeAt(0);
    // Hash array to record letter count
    let helperArr: number[] = new Array(26).fill(0);

    // Record letters in magazine (add count in array)
    for (let i = 0; i < magazine.length; i++) {
        helperArr[magazine.charCodeAt(i) - pivot]++;
    }
    // Record letters in ransom note (minus count in array)
    for (let i = 0; i < ransomNote.length; i++) {
        let index = ransomNote.charCodeAt(i) - pivot;
        helperArr[index]--;
        // If any value is negative, means letters in magazine is not enough to use in ransom note
        if (helperArr[index] < 0) return false;
    }
    return true;
};

Conclusion

Another hash methods question, but use array would be the most efficiency way to do it. Always think the choice between array, set, and map, choose the most simple and efficient one!