383. Ransom Note

Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.

Each letter in the magazine string can only be used once in your ransom note.

 

Example 1:

Input: ransomNote = "a", magazine = "b"
Output: false

Example 2:

Input: ransomNote = "aa", magazine = "ab"
Output: false

Example 3:

Input: ransomNote = "aa", magazine = "aab"
Output: true

 

Constraints:

  • You may assume that both strings contain only lowercase letters.

Rust Solution

struct Solution;

use std::collections::HashMap;

impl Solution {
    fn can_construct(ransom_note: String, magazine: String) -> bool {
        let mut hm: HashMap<char, i32> = HashMap::new();
        if ransom_note.len() > magazine.len() {
            return false;
        }
        if ransom_note == magazine {
            return true;
        }
        for c in magazine.chars() {
            let e = hm.entry(c).or_default();
            *e += 1;
        }
        for c in ransom_note.chars() {
            if let Some(v) = hm.get_mut(&c) {
                *v -= 1;
                if *v < 0 {
                    return false;
                }
            } else {
                return false;
            }
        }
        true
    }
}

#[test]
fn test() {
    let r = "a".to_string();
    let m = "b".to_string();
    assert_eq!(Solution::can_construct(r, m), false);
    let r = "aa".to_string();
    let m = "ab".to_string();
    assert_eq!(Solution::can_construct(r, m), false);
    let r = "aa".to_string();
    let m = "aab".to_string();
    assert_eq!(Solution::can_construct(r, m), true);
}

Having problems with this solution? Click here to submit an issue on github.