Hash Tables: Ransom Note - Hacker Rank Solution

Check out the resources on the page's right side to learn more about hashing. The video tutorial is by Gayle Laakmann McDowell, author of the best-selling interview book Cracking the Coding Interview.

Harold is a kidnapper who wrote a ransom note, but now he is worried it will be traced back to him through his handwriting.

He found a magazine and wants to know if he can cut out whole words from it and use them to create an untraceable replica of his ransom note. The words in his note are case-sensitive and he must use only whole words available in the magazine. He cannotuse substrings or concatenation to create the words he needs.

Given the words in the magazine and the words in the ransom note, print Yes if he can replicate his ransom note exactly using whole words from the magazine; otherwise, print No.

For example, the note is "Attack at dawn". The magazine contains only "attack at dawn". The magazine has all the right words, but there's a case mismatch. The answer is .

Function Description

Complete the checkMagazine function in the editor below. It must print  if the note can be formed using the magazine, or .

checkMagazine has the following parameters:

• magazine: an array of strings, each a word in the magazine
• note: an array of strings, each a word in the ransom note

Input Format

The first line contains two space-separated integers,  and , the numbers of words in the  and the ..
The second line contains  space-separated strings, each .
The third line contains  space-separated strings, each .

Constraints

• .
• Each word consists of English alphabetic letters (i.e.,  to  and  to ).

Output Format

Print Yes if he can use the magazine to create an untraceable replica of his ransom note. Otherwise, print No.

Sample Input 0

6 4
give me one grand today night
give one grand today

Sample Output 0

Yes

Sample Input 1

6 5
two times three is not four
two times two is four

Sample Output 1

No

Explanation 1

'two' only occurs once in the magazine.

Sample Input 2

7 4
ive got a lovely bunch of coconuts
ive got some coconuts

Sample Output 2

No

Explanation 2

Harold's magazine is missing the word .

Hash Tables: Ransom Note - Hacker Rank Solution

We have a multiset of words in a magazine, , and a multiset of words in a ransom note, . If  is contained in , then we print Yes because we can recreate the note; otherwise, we print No.

Approach

To solve this challenge, we use two maps:

1. , which maps each word in  to its frequency.
2. , which maps each word in  to its frequency.

Because we only care that all the words in  are contained in , we simply iterate over 's keyset and answer the following questions:

1. Does the key (from 's keyset) exist in ?
2. If the key exists in both maps, is the value associated with that key in  less than the value associated with the key in ?

If we answer no to the first question, we know that the magazine doesn't contain all the whole words we need to recreate the note. If we answer no to the second question, then we know that the word exists in the magazine but it simply does not occur enough times for us to recreate the entire note.

Problem Setter's code:

C++

#include <bits/stdc++.h>

using namespace std;

int main() {
    int m;  //number of words in magazine
    int n;  //number of words in notes
    cin >> m >> n;
    
    map<string, int> magazine; //map to store words in magazine with its frequency
    map<string, int> note;    //map to store words in notes with its frequency
    
    string word;
    
    for(int i = 0; i < m; i++) {
        cin >> word;
        magazine[word]++;
    }
    
    for(int i = 0; i < n; i++) {
        cin >> word;
        note[word]++;
    }
    
    map<string, int> :: iterator it;
    bool success = 1;
    
    //iterate over note map to check whether all words are present in map or not
    for(it = note.begin(); it != note.end(); it++) {
        if(magazine[it->first] < it->second) {
            success = 0;
            break;
        }
    }
    
    if(success) {
        cout << "Yes";
    }
    else {
        cout << "No";
    }

    return 0;
}

Problem Tester's code:

Java

import java.util.*;

public class Solution {
    Map<String, Integer> magazineMap;
    Map<String, Integer> noteMap;
    
    public Solution(String magazine, String note) {
        this.noteMap = new HashMap<String, Integer>();
        this.magazineMap = new HashMap<String, Integer>();
        
        // Must use an object instead of a primitive because it may be assigned a null reference.
        Integer occurrences;
        
        for(String s : magazine.split("[^a-zA-Z]+")) {
            occurrences = magazineMap.get(s);
            
            if(occurrences == null) {
                magazineMap.put(s, 1);
            }
            else {
                magazineMap.put(s, occurrences + 1);
            }
        }
        
        for(String s : note.split("[^a-zA-Z]+")) {
            occurrences = noteMap.get(s);
            
            if(occurrences == null) {
                noteMap.put(s, 1);
            }
            else {
                noteMap.put(s, occurrences + 1);
            }
        }
        
    }
    
    public void solve() {
        boolean canReplicate = true;
        for(String s : noteMap.keySet()) {
            if(!magazineMap.containsKey(s) || (magazineMap.get(s) < noteMap.get(s)) ) {
                canReplicate = false;
                break;
            }
        }
        
        System.out.println( (canReplicate) ? "Yes" : "No" );
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        
        // Eat whitespace to beginning of next line
        scanner.nextLine();
        
        Solution s = new Solution(scanner.nextLine(), scanner.nextLine());
        scanner.close();
        
        s.solve();
    }
}