383. Ransom Note Leetcode Rust solution

Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.

Each letter in magazine can only be used once in ransomNote.

Solution:

The Full Code

rust

use std::collections::HashMap;

impl Solution {
    pub fn can_construct(ransom_note: String, magazine: String) -> bool {
        let mut freq = HashMap::new();

        for ch in magazine.chars() {
            *freq.entry(ch).or_insert(0) += 1;
        }

        for ch in ransom_note.chars() {
            if let Some(count) = freq.get_mut(&ch) {
                if *count == 0 {
                    return false;
                }
                *count -= 1;
            } else {
                return false;
            }
        }

        true
    }
}

Explaining It Line by Line

Line 1: use std::collections::HashMap;

Okay, so picture this: Rust has a big toolbox called the standard library (or std for short). Inside that toolbox, there’s a section labeled collections, which is full of handy data structures. One of those is HashMap, a key-value storage thing—like a dictionary or a phonebook. Here, we’re saying, “Hey Rust, let me borrow HashMap from your std::collections shelf so I can use it in my code.” The use keyword is just us grabbing that tool and putting it on our workbench.

Line 2: impl Solution {

Now we’re getting into the meat of it. Imagine Solution as a little blueprint or class (it’s actually a struct in Rust terms) that LeetCode gave us. The impl keyword is Rust’s way of saying, “I’m about to define some functions for this Solution thing.” The curly brace { is like opening the door to a room where we’ll write those functions.

Line 3: pub fn can_construct(ransom_note: String, magazine: String) -> bool {

This is where the action starts! Let’s break it down:

pub means “public”—this function can be called from outside the Solution struct.
fn is Rust shorthand for “function”—we’re defining one now.
can_construct is the name of our function. It’s like a question: “Can I build ransom_note using the letters in magazine?”
Inside the parentheses, we’ve got two inputs:
- ransom_note: String → The note we’re trying to make (a String is just text in Rust).
- magazine: String → The pile of letters we can use to make it.
-> bool tells us the function will spit out a true or false answer (a Boolean).
The { opens up the function’s body—like flipping to a fresh page to start writing.

Line 4: let mut freq = HashMap::new();

Here’s where we set up our counting system. Think of freq as a little notebook where we’ll jot down how many times each letter appears in magazine.

let is how we create a new variable in Rust.
mut means “mutable”—we’re allowed to change this notebook later.
freq is the name we’re giving it (short for “frequency”).
HashMap::new() creates a fresh, empty HashMap. In this notebook, the keys will be letters (like ‘a’ or ‘b’), and the values will be numbers (how many times we’ve got that letter). The semicolon ; says, “I’m done with this line!”

Line 5: for ch in magazine.chars() {

Now we’re flipping through magazine letter by letter.

for starts a loop—it’s like saying, “Let’s go through this one by one.”
ch is the nickname we give each letter as we look at it (short for “character”).
magazine.chars() takes our magazine string and turns it into a lineup of characters we can step through. For example, if magazine is “aab”, this gives us ‘a’, ‘a’, ‘b’.
The { opens the loop’s body—what we’ll do for each letter.

Line 6: *freq.entry(ch).or_insert(0) += 1;

This line is a bit tricky, but it’s super cool! Imagine we’re tallying letters in our notebook.

freq.entry(ch) is like looking up ch (the current letter) in our HashMap. It’s asking, “Have I seen this letter before?”
- If yes, it hands us the existing tally.
- If no, it gets ready to add a new entry.
.or_insert(0) says, “If this letter isn’t in the notebook yet, start its count at 0.”
* is Rust’s way of saying, “Get me the actual number, not just a pointer to it.” (Rust loves safety, so it uses references a lot—this unwraps one.)
+= 1 means “add 1 to whatever number we’ve got.” So if ‘a’ had a count of 1, it becomes 2.

For example, if magazine is “aab”, after this loop, our notebook looks like:

'a': 2
'b': 1

Line 7: for ch in ransom_note.chars() {

Now we switch gears and start checking ransom_note. This is another loop, just like before, but now we’re stepping through the letters we need instead of the ones we have. Same deal: ch is each letter, and .chars() gives us the lineup.

Line 8: if let Some(count) = freq.get_mut(&ch) {

This line is about checking our supplies. Here’s what’s happening:

freq.get_mut(&ch) looks up ch in our notebook and gives us a mutable reference to its count—if it’s there. The & means we’re borrowing ch to peek at it.
In Rust, get_mut returns an Option—either Some(value) if the letter exists, or None if it doesn’t.
if let Some(count) = is a neat trick. It says, “If we got a Some with a count, call it count and run the code inside the braces. If we got None, skip to the else part.”

Line 9: if *count == 0 { return false; }

Inside the if let, we’re checking our stock.

*count grabs the actual number of letters we have left (that * again is unwrapping the reference).
== 0 asks, “Are we out of this letter?”
If yes, return false; kicks us out of the function with a “Nope, can’t do it!” We’re done early because we don’t have enough of that letter.

Line 10: *count -= 1;

If we’re not out of the letter, we use one up.

*count gets the number.
-= 1 subtracts 1 from it. So if we had 2 ‘a’s, now we have 1. This tracks that we’ve “spent” a letter from magazine.

Line 11: else { return false; }

This ties back to Line 8’s if let. If freq.get_mut(&ch) gave us None (meaning the letter isn’t in our notebook at all), we hit this else. That’s bad news—we need a letter we don’t have, so we return false and call it quits.

Line 12: true

If we make it through the whole ransom_note loop without bailing out with false, it means we had enough letters for everything! So we return true—mission accomplished!

Let’s Try an Example

Say ransom_note = “aa” and magazine = “aab”.

Build the notebook from magazine:
- ‘a’ → count goes to 1, then 2.
- ‘b’ → count goes to 1.
- Notebook: {‘a’: 2, ‘b’: 1}.
Check ransom_note:
- First ‘a’: Found it, count is 2, subtract 1 → {‘a’: 1, ‘b’: 1}.
- Second ‘a’: Found it, count is 1, subtract 1 → {‘a’: 0, ‘b’: 1}.
We used all the letters we needed, so we return true.

How Fast Is It?

Counting letters in magazine: Takes time based on its length (let’s call it m steps).
Checking ransom_note: Takes time based on its length (say n steps).
Total: O(m + n)—pretty quick, even for big strings!

Wrapping Up

This code is like a clever little accountant: it tallies up what we’ve got, checks what we need, and makes sure we don’t overspend. It’s efficient, handles all the tricky cases (like missing letters), and fits perfectly into Rust’s style. If you’re submitting this to LeetCode, you’re golden! What do you think—did that clear things up?

383. Ransom Note Leetcode Rust solution

Comments

Leave a Reply Cancel reply