Leetcode 383. Ransom Note

Problem Description

In this problem, you are given two strings. One string represents a ransom note, and the other string represents a collection of characters from various magazines. The aim is to determine whether it is possible to construct the ransom note from the characters found in the magazines.

You need to write a function canConstruct(ransomNote, magazine) that takes these two strings as parameters, and returns true if the ransom note can be constructed from the characters in the magazines, or false otherwise.

The constraints are that each letter in the magazine may only be used once in the ransom note, and that both strings only contain lowercase letters.

Example

For instance, if the ransom note is "aa" and the magazines have the characters "aab", the function would return true. This is because there are sufficient 'a' characters (2) in the magazines to construct the ransom note.

However, if the ransom note is "aa" and the magazines have the characters "ab", the function would return false. This is because there are not enough 'a' characters in the magazines to construct the ransom note.

Solution Approach

The solution for this problem uses a data structure known as a count table, which in this case is a vector of integers. The indexes of this vector represent the ASCII values of the characters from a to z.

The basic idea is to iterate over the magazine string. For each character, we increment the count in the count table at the index corresponding to the ASCII value of that character.

After updating the count table, we then iterate over the ransomNote string. For each character, we decrement the count in the count table at the index corresponding to the ASCII value of that character. If at any point the count in the count table goes negative, we return false because this means that there aren't enough characters in the magazine to form the ransomNote.

If we finish the iteration without the count going negative, we return true because this means there were enough characters in the magazine to form the ransomNote.

Class Definitions

Java

1
2java
3class Solution {
4    public boolean canConstruct(String ransomNote, String magazine) {
5        int[] count = new int[128];  // declare a count table of size 128
6
7        // iterate over the magazine string
8        for (char c : magazine.toCharArray()) {
9            // increment the count for each character
10            count[c]++;
11        }
12
13        // iterate over the ransom note string
14        for (char c : ransomNote.toCharArray()) {
15            // decrement the count for each character
16            count[c]--;
17            
18            // if count becomes negative, return false
19            if (count[c] < 0) {
20                return false;
21            }
22        }
23        
24        return true;
25    }
26}

Python

1
2python
3class Solution:
4    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
5        # create a dictionary to hold the count of each character in magazine
6        char_count = {}
7        
8        # count the characters in magazine
9        for char in magazine:
10            char_count[char] = char_count.get(char, 0) + 1
11        
12        # check if ransomNote can be constructed
13        for char in ransomNote:
14            if char not in char_count or char_count[char] == 0:
15                return False
16            char_count[char] -= 1
17        
18        return True

###JavaScript

1
2javascript
3class Solution {
4    canConstruct(ransomNote, magazine) {
5        const count = new Array(128).fill(0);  // declare a count table of size 128
6
7        // iterate over the magazine string
8        for (let c of magazine) {
9            // increment the count for each character
10            count[c.charCodeAt(0)]++;
11        }
12
13        // iterate over the ransom note string
14        for (let c of ransomNote) {
15            // decrement the count for each character
16            if (--count[c.charCodeAt(0)] < 0)
17                return false;
18        }
19
20        return true;
21    }
22}

C++

1
2c++
3class Solution {
4public:
5    bool canConstruct(string ransomNote, string magazine) {
6        vector<int> count(128);
7
8        for (const char c : magazine)
9            ++count[c];
10
11        for (const char c : ransomNote)
12            if (--count[c] < 0)
13                return false;
14
15        return true;
16    }
17};

C#

1
2csharp
3public class Solution {
4    public bool CanConstruct(string ransomNote, string magazine) {
5        int[] count = new int[128];  // declare a count table of size 128
6
7        // iterate over the magazine string
8        foreach (char c in magazine) {
9            // increment the count for each character
10            count[c]++;
11        }
12
13        // iterate over the ransom note string
14        foreach (char c in ransomNote) {
15            // decrement the count for each character
16            count[c]--;
17            
18            // if count becomes negative, return false
19            if (count[c] < 0) {
20                return false;
21            }
22        }
23        
24        return true;
25    }
26}

Testing the Solutions

After implementing the solution, it is also important to test it to ensure its correctness. This can be done by supplying some test cases to the function and comparing the expected outputs. Below are some test cases that you could use:

1
2java
3Solution solution = new Solution();
4
5System.out.println(solution.canConstruct("a", "b"));        // should output false
6System.out.println(solution.canConstruct("aa", "ab"));      // should output false
7System.out.println(solution.canConstruct("aa", "aab"));     // should output true
8System.out.println(solution.canConstruct("abacd", "abcde"));// should output False

1
2python
3s= Solution()
4print(s.canConstruct("a", "b"))         # should output false
5print(s.canConstruct("aa", "ab"))       # should output false
6print(s.canConstruct("aa", "aab"))      # should output true
7print(s.canConstruct("abacd", "abcde")) # should output False

1
2javascript
3let s = new Solution();
4
5console.log(s.canConstruct("a", "b"));  // should output false
6console.log(s.canConstruct("aa", "ab")); // should output false
7console.log(s.canConstruct("aa", "aab"));  // should output true
8console.log(s.canConstruct("abacd", "abcde"));// should output False

1
2c++
3Solution solution;
4
5std::cout << std::boolalpha
6          << solution.canConstruct("a", "b") << "\n"      // should output false
7          << solution.canConstruct("aa", "ab") << "\n"    // should output false
8          << solution.canConstruct("aa", "aab") << "\n"    // should output true
9          << solution.canConstruct("abacd", "abcde");    // should output False

1
2csharp
3Solution solution = new Solution();
4
5Console.WriteLine(solution.CanConstruct("a", "b"));     // should output false
6Console.WriteLine(solution.CanConstruct("aa", "ab"));    // should output false
7Console.WriteLine(solution.CanConstruct("aa", "aab"));     // should output true
8Console.WriteLine(solution.CanConstruct("abacd", "abcde"));// should output False

In summary, to solve this problem you just need to take advantage of a simple data structure, a count table or a dictionary, where you can keep counting the number of appearances of each character from the given magazine. You then iterate over the Ransom Note string checking if the current character count goes below zero. If it does, you can then conclude that the Ransom Note cannot be constructed from the Magazine. Otherwise, the Ransom Note can be formed from the Magazine.