LeetCode 383. Ransom Note

[quinnwencn]

Description

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.

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:

1 <= ransomNote.length, magazine.length <= 105
ransomNote and magazine consist of lowercase English letters.

[quinnwencn]

Analysis

There are only lowercase English letters in both magazine and ransomNotes. We can use a 26-sized array to calculate the number of letters in magazine and compare them with ransomNotes.

Solution written in Cpp

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        std::array<uint32_t, 26> alpha {0};
        for (auto c: magazine) {
            alpha[c - 'a']++;
        }

        for (auto c: ransomNote) {
            if (alpha[c - 'a'] <= 0) {
                return false;
            }

            alpha[c - 'a']--;
        }

        return true;
    }
};

Solution written in Rust

impl Solution {
    pub fn can_construct(ransom_note: String, magazine: String) -> bool {
        let mut count: [i32; 26] = [0; 26];
        magazine
            .chars()
            .for_each(|char| {
                let index = char as usize - 'a' as usize;
                count[index] += 1;
            });

        let mut res = true;
        ransom_note
            .chars()
            .for_each(|char| {
                let index = char as usize - 'a' as usize;
                if count[index] == 0 {
                    res = false;
                } else {
                    count[index] -= 1;
                }
            });

        res
    }
}