Ransom Note (leetcode)

_provided.rs

/**
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.

Note:
You may assume that both strings contain only lowercase letters.

  canConstruct("a", "b") -> false
  canConstruct("aa", "ab") -> false
  canConstruct("aa", "aab") -> true
 
View problem on leetcode: https://leetcode.com/problems/ransom-note/

Execute on the rust playground: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=e3f2bd039c8b009c3bfcf0de757e9ad6
**/

pub struct Solution {}

solution.rs

// for the HashMap solution
use std::collections::{hash_map::Entry, HashMap};

impl Solution {
    /// # Solution 1: Use a HashMap.
    /// Build a map of counts of the letters in string
    /// Iterate through the ransom_note checking and decrementing the count in the 
    /// HashMap.
    /// Any missing letters false, else true

    pub fn can_construct_hashmap(ransom_note: String, magazine: String) -> bool {
        
        let mut m = HashMap::with_capacity(26);
        for c in magazine.chars() {
            *m.entry(c).or_insert(0) += 1
        }
        
        for c in ransom_note.chars() {
            // entry() returns an enum over Entry::Occupied or
            // Entry::NotOccupied
            if let Entry::Occupied(mut o) = m.entry(c) {
                let v = o.get_mut();
                if *v < 1 {
                    return false;
                }
                *v -= 1;
            } else {
                // Entry::NotOccupied
                return false;
            }
        }
        true
    }
    
    /// # Solution 2: Use an array.
    /// Because we are guaranteed strings that only contain a..z, we build a 26 element Vec to store
    /// the letter counts from magazine, indexed by char offset from 'a'
    ///
    /// Algorithm is the same:
    /// Build a Vec of counts of the letters in string, indexed by the offset between the char and 'a'
    /// Iterate through the ransom_note checking and decrementing the count in the 
    /// vector.
    /// Any missing letters false, else true
  
    pub fn can_construct_array(ransom_note: String, magazine: String) -> bool {
        // store counts per char in a vector.  We are guaranteed strings with only chars [a..z]
        let mut m = vec![0; 26];
        const OFFSET: usize = 'a' as usize;
        for c in magazine.chars() {
            m[c as usize - OFFSET] += 1
        }
        // println!("{:?}", m);
        for c in ransom_note.chars() {
            let i = c as usize - OFFSET;
            if m[i] == 0 {
                return false;
            }
            m[i] -= 1;
        }
        true
    }
}

tests.rs

#[test]
fn no_match_hash_solution() {
    let ransom_note = "a";
    let magazine = "b";
    assert!(!Solution::can_construct_hashmap(
        ransom_note.to_string(),
        magazine.to_string()
    ));
}

#[test]
fn match_hash_solution() {
    let ransom_note = "a";
    let magazine = "a";
    assert!(Solution::can_construct_hashmap(
        ransom_note.to_string(),
        magazine.to_string()
    ));
}

// three provided test cases:
#[test]
fn  provided_test_cases_hash_solution() {
    //failure
    let ransom_note = "a";
    let magazine = "b";
    assert!(!Solution::can_construct_hashmap(
        ransom_note.to_string(),
        magazine.to_string()
    ));

    //failure
    let ransom_note = "aa";
    let magazine = "ab";
    assert!(!Solution::can_construct_hashmap(
        ransom_note.to_string(),
        magazine.to_string()
    ));

    //success
    let ransom_note = "aa";
    let magazine = "aba";
    assert!(Solution::can_construct_hashmap(
        ransom_note.to_string(),
        magazine.to_string()
    ));
}

#[test]
fn no_match_array_solution() {
    let ransom_note = "a";
    let magazine = "b";
    assert!(!Solution::can_construct_array(
        ransom_note.to_string(),
        magazine.to_string()
    ));
}

#[test]
fn match_array_solution() {
    let ransom_note = "a";
    let magazine = "a";
    assert!(Solution::can_construct_array(
        ransom_note.to_string(),
        magazine.to_string()
    ));
}

// three provided test cases:
#[test]
fn provided_test_cases_array_solution() {
    //failure
    let ransom_note = "a";
    let magazine = "b";
    assert!(!Solution::can_construct_array(
        ransom_note.to_string(),
        magazine.to_string()
    ));

    //failure
    let ransom_note = "aa";
    let magazine = "ab";
    assert!(!Solution::can_construct_array(
        ransom_note.to_string(),
        magazine.to_string()
    ));

    //success
    let ransom_note = "aa";
    let magazine = "aba";
    assert!(Solution::can_construct_array(
        ransom_note.to_string(),
        magazine.to_string()
    ));
}