Determine whether a magazine contains the words needed for a ransom note

Question

This is a website Question on Hackrrank called Hash Tables: Ransom Note:

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

Here is an example input:

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

Output: Yes

And another:

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

Output: No

---

def checkMagazine(magazine, note):

    #Creating 2 Empty Dictionaries for the "Magazine" and the "Note" then filling them up
    UniqueWordsMag = set(magazine)
    UniqueCountMag = [0]*len(UniqueWordsMag)
    UniqueWordDictMag = dict(zip(UniqueWordsMag, UniqueCountMag))

    UniqueWordsNote= set(note)
    UniqueCountNote = [0]*len(UniqueWordsNote)
    UniqueWordDictNote = dict(zip(UniqueWordsNote, UniqueCountNote))

    for i in magazine:
        if i in list(UniqueWordDictMag.keys()):
            UniqueWordDictMag[i] += 1

    for i in note:
        if i in list(UniqueWordDictNote.keys()):
            UniqueWordDictNote[i] += 1


    #Checking for existance in the magazine then checking for the correct count, print no if it does not fulfil conditions
    Success = False
    DesiredCount = len(note)
    Count = 0

    for index,i in enumerate(UniqueWordsNote):
        if i in list(UniqueWordDictMag.keys()):
            if UniqueWordDictNote[i] <= UniqueWordDictMag[i]:
                Count += UniqueWordDictNote[i]
            else:
                break
        else:
            break

    if Count == DesiredCount:
        Success = True
        print("Yes")
    else:
        print("No")

It's called from this main program, that's provided by the challenge:

def main():
    mn = input().split()

    m = int(mn[0])

    n = int(mn[1])

    magazine = input().rstrip().split()

    note = input().rstrip().split()

    checkMagazine(magazine, note)

if __name__ == "__main__":
    main()

My code is currently taking too long on some lists (e.g. lists of size 30,000 or more). Are there any optimisations I can make to make this a bit more legible and faster?

Answer 1

You're making it enormously complicated. This is a job for Counter:

from collections import Counter

def checkMagazine(magazine, note):
    print('No' if Counter(note) - Counter(magazine) else 'Yes')

Answer 2

You should use Counter, but even for not using Counter you made it very complicated. Doing it with dict and keeping your structure, you could do this:

def checkMagazine(magazine, note):
    
    mag_ctr = dict.fromkeys(magazine, 0)
    note_ctr = dict.fromkeys(note, 0)
    
    for word in magazine:
        mag_ctr[word] += 1
    
    for word in note:
        note_ctr[word] += 1
    
    for word in note_ctr:
        if note_ctr[word] > mag_ctr.get(word, 0):
            print('No')
            break
    else:
        print('Yes')

Just for fun, while I'm here... this trivial solution also got accepted despite being slow:

def checkMagazine(magazine, note):
    try:
        for word in note:
            magazine.remove(word)
        print('Yes')
    except:
        print('No')

I like it because it's simple. We can do a similar but fast one by using a Counter for the magazine (none needed for the note, saving memory compared to two Counters):

def checkMagazine(magazine, note):
    available = Counter(magazine)
    for word in note:
        if not available[word]:
            print('No')
            break
        available[word] -= 1
    else:
        print('Yes')

Answer 3

Counting the number of occurrences of an item already exists in the list.count(item) function. To continue with the approach of jumping out of code as soon as possible with your break out of a for loop, we can use a generator inside an any evaluation like so:

def check_magazine(magazine, note):
    print("No" if any(note.count(word) > magazine.count(word) for word in set(note)) else "Yes")

Answer 4

General (non-performance) review:

There are several variables assigned but never used. For example:

    mn = input().split()
    m = int(mn[0])
    n = int(mn[1])

We never use m or n, so this can just be replaced by

    input()

(I later discovered that main() was provided by the challenge, so you're not to blame for this. OTOH, there's nothing to stop you improving the boilerplate you were given!)

Similarly:

    Success = True
    print("Yes")

Success is never used; just remove it.

As noted elsewhere,

#Creating 2 Empty Dictionaries for the "Magazine" and the "Note" then filling them up
UniqueWordsMag = set(magazine)
UniqueCountMag = [0]*len(UniqueWordsMag)
UniqueWordDictMag = dict(zip(UniqueWordsMag, UniqueCountMag))

UniqueWordsNote= set(note)
UniqueCountNote = [0]*len(UniqueWordsNote)
UniqueWordDictNote = dict(zip(UniqueWordsNote, UniqueCountNote))

for i in magazine:
    if i in list(UniqueWordDictMag.keys()):
        UniqueWordDictMag[i] += 1

for i in note:
    if i in list(UniqueWordDictNote.keys()):
        UniqueWordDictNote[i] += 1

is much simpler using a Counter:

import collections
magazine_words = collections.Counter(magazine)
note_words = collections.Counter(note)

And the test

#Checking for existance in the magazine then checking for the correct count, print no if it does not fulfil conditions
Success = False
DesiredCount = len(note)
Count = 0

for index,i in enumerate(UniqueWordsNote):
    if i in list(UniqueWordDictMag.keys()):
        if UniqueWordDictNote[i] <= UniqueWordDictMag[i]:
            Count += UniqueWordDictNote[i]
        else:
            break
    else:
        break

if Count == DesiredCount:

reduces to just

if magazine_words & note_words == note_words:

Answer 5

Instead of:

for i in magazine:
        if i in list(UniqueWordDictMag.keys()):
            UniqueWordDictMag[i] += 1

    for i in note:
        if i in list(UniqueWordDictNote.keys()):
            UniqueWordDictNote[i] += 1

Avoid creating a list and just iterate over the keys

for i in magazine:
        if i in UniqueWordDictMag.keys():
            UniqueWordDictMag[i] += 1

    for i in note:
        if i in UniqueWordDictNote.keys():
            UniqueWordDictNote[i] += 1