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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.