383. Ransom Note – Leetcode Solutions

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

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        # Count the frequency of each letter in magazine
        magazine_count = Counter(magazine)
        
        # Iterate over each character in ransomNote and check if it's available in magazine
        for char in ransomNote:
            # If the character is not available or the count is insufficient, return False
            if magazine_count[char] <= 0:
                return False
            # Otherwise, decrement the count of the character in magazine
            magazine_count[char] -= 1
        
        # If all characters in ransomNote are satisfied, return True
        return True

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        // Step 1: Create a frequency array for storing character counts for 'a' to 'z'.
        vector<int> charCount(26, 0);
        
        // Step 2: Count each character in magazine and store it in the charCount array.
        for (char ch : magazine) {
            charCount[ch - 'a']++;  // 'a' has an ASCII value of 97, so 'ch - 'a'' gives an index from 0 to 25
        }
        
        // Step 3: Iterate through ransomNote to check if we have enough characters.
        for (char ch : ransomNote) {
            // If the current character's count is zero, return false as we don't have enough characters
            if (charCount[ch - 'a'] == 0) {
                return false;
            }
            // Otherwise, decrement the character count to reflect usage
            charCount[ch - 'a']--;
        }
        
        // Step 4: If we successfully go through the ransomNote, return true
        return true;
    }
};

var canConstruct = function(ransomNote, magazine) {
    // Step 1: Create a frequency map for characters in the magazine
    // This map will store the count of each character in the magazine string
    let magazineMap = {};

    // Loop over each character in the magazine string
    for (let char of magazine) {
        // If the character is already in the map, increment its count
        // Otherwise, initialize it to 1
        magazineMap[char] = (magazineMap[char] || 0) + 1;
    }

    // Step 2: Check if ransomNote can be constructed
    // by looping over each character in ransomNote
    for (let char of ransomNote) {
        // If the character is not in the magazineMap or its count is zero,
        // we can't construct the ransomNote, so return false
        if (!magazineMap[char] || magazineMap[char] === 0) {
            return false;
        }
        // If the character is found, decrement its count in the map
        magazineMap[char]--;
    }

    // If all characters in ransomNote are found with sufficient count in magazine
    // then we can construct the ransomNote, so return true
    return true;
};

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        // Step 1: Create an array to store the frequency of each letter in magazine
        // Since there are only lowercase English letters, we need an array of size 26.
        int[] letterCounts = new int[26];
        
        // Step 2: Populate the frequency array based on the letters in the magazine
        // We calculate the index by subtracting 'a' to map 'a'-'z' to 0-25.
        for (char c : magazine.toCharArray()) {
            letterCounts[c - 'a']++;
        }
        
        // Step 3: Iterate through each character in ransomNote
        for (char c : ransomNote.toCharArray()) {
            // Decrease the count for the current character
            letterCounts[c - 'a']--;
            
            // Step 4: If count goes below zero, it means magazine does not
            // have enough of this character to form ransomNote, so return false.
            if (letterCounts[c - 'a'] < 0) {
                return false;
            }
        }
        
        // Step 5: If we successfully process all characters in ransomNote,
        // it means we can construct ransomNote from magazine, so return true.
        return true;
    }
}