Ransom Note

EasyHash mapLeetCode 383 ↗World 1-16

0:00 / 0:00

Can the note be cut from the magazine? Count every magazine letter, then spend one per note letter and fail the moment a count runs out.

▼

The problem

LeetCode 383 (Easy). Given two strings ransomNote and magazine, return true if ransomNote can be built from the letters of magazine, each magazine letter used at most once, and false otherwise. Both strings are lowercase English letters.

Examples (LeetCode's): ("a", "b") → false, ("aa", "ab") → false, ("aa", "aab") → true.

TRY IT ON LEETCODE ▶

The solution

def canConstruct(ransomNote, magazine):
    count = [0] * 26
    for ch in magazine:
        count[ord(ch) - ord('a')] += 1
    for ch in ransomNote:
        i = ord(ch) - ord('a')
        if count[i] == 0:
            return False
        count[i] -= 1
    return True

Transcript

Ransom Note. You get two strings: a ransom note and a magazine. Can you build the note from the magazine's letters? Each magazine letter works only once.

Note A, magazine B: false. There's no A. Note A A, magazine A B: false, only one A. Note A A, magazine A A B: true. Two A's, and the B is left over.

The naive way: for each note letter, scan the magazine for an unused copy and cross it out. Loot from toolbox takes ten checks. With m note letters and n magazine letters, that's up to m times n checks.

Better: count, then spend. Pour the magazine into a type case with twenty-six drawers, one per letter. Toolbox puts three blocks in O, and one each in T, L, B and X. Then each note letter takes a block from its drawer. An empty drawer means false. If every letter gets one, true.

In code, the drawers are an array of twenty-six counters. One loop over the magazine adds one. One loop over the note checks for zero, then subtracts one.

Let's run A A from A A B. Counting gives A two and B one. The first A takes a block: one left. The second A takes the last. Every letter fit, so true. With A B as the magazine, the second A finds an empty drawer: false.

Each string is read once: order m plus n time. Twenty-six counters never grow: constant space.

Count the magazine, spend on the note, stop at an empty drawer. That's Ransom Note.