Visit original link: 383. Ransom Note - LeetCode Python/Java/C++/JS/C#/Go/Ruby Solutions for a better experience!

LeetCode link: 383. Ransom Note, difficulty: Easy.

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.

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

Output: false

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

Output: false

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

Output: true

• 1 <= ransomNote.length, magazine.length <= 10^5
• ransomNote and magazine consist of lowercase English letters.

1. This question is equivalent to asking whether magazine can contain all the characters in ransomNote.

2. First count magazine to get the number of words corresponding to each character, and store the result in Map. Each time is an addition one operation.

3. What to do next?

   Click to view the answer

   Traverses `ransomNote` and subtracts one from the number corresponding to the current character (reverse operation). If the number of a character is less than 0, return `false`.

1. First count the characters in magazine, and store the results in Map.

   charToCount = new Map()
   
   for (character in magazine) {
     charToCount[character] += 1
   }

2. Then, traverse ransomNote and perform reverse operations on the data in Map. If the count of a character is less than 0, return false.

   charToCount = new Map()
   
   for (character in magazine) {
     charToCount[character] += 1
   }
   
   for (character in ransomNote) {
     charToCount[character] -= 1
   
     if (charToCount[character] < 0) {
       return false
     }
   }
   
   return true

• Time complexity: O(N).
• Space complexity: O(N).

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        var charToCount = new HashMap<Character, Integer>();

        for (var character : magazine.toCharArray()) {
            charToCount.put(character, charToCount.getOrDefault(character, 0) + 1);
        }

        for (var character : ransomNote.toCharArray()) {
            charToCount.put(character, charToCount.getOrDefault(character, 0) - 1);

            if (charToCount.get(character) < 0) {
                return false;
            }
        }

        return true;
    }
}

# from collections import defaultdict

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        char_to_count = defaultdict(int)

        for char in magazine:
            char_to_count[char] += 1

        for char in ransomNote:
            char_to_count[char] -= 1

            if char_to_count[char] < 0:
                return False

        return True

var canConstruct = function (ransomNote, magazine) {
  const charToCount = new Map()

  for (const character of magazine) {
    charToCount.set(character, (charToCount.get(character) || 0) + 1)
  }

  for (const character of ransomNote) {
    charToCount.set(character, (charToCount.get(character) || 0) - 1)

    if (charToCount.get(character) < 0) {
      return false
    }
  }

  return true
};

public class Solution
{
    public bool CanConstruct(string ransomNote, string magazine)
    {
        var charToCount = new Dictionary<char, int>();

        foreach (char character in magazine)
            charToCount[character] = charToCount.GetValueOrDefault(character, 0) + 1;

        foreach (char character in ransomNote)
        {
            charToCount[character] = charToCount.GetValueOrDefault(character, 0) - 1;

            if (charToCount[character] < 0)
            {
                return false;
            }
        }

        return true;
    }
}

def can_construct(ransom_note, magazine)
  char_to_count = Hash.new(0)

  magazine.each_char { |c| char_to_count[c] += 1 }

  ransom_note.each_char do |c|
    char_to_count[c] -= 1
    return false if char_to_count[c] < 0
  end

  true
end

func canConstruct(ransomNote string, magazine string) bool {
    charToCount := make(map[rune]int)
    
    for _, char := range magazine {
        charToCount[char]++
    }
    
    for _, char := range ransomNote {
        charToCount[char]--
        
        if charToCount[char] < 0 {
            return false
        }
    }
    
    return true
}

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        unordered_map<char, int> char_to_count;
        
        for (char character : magazine) {
            char_to_count[character]++;
        }
        
        for (char character : ransomNote) {
            char_to_count[character]--;
            
            if (char_to_count[character] < 0) {
                return false;
            }
        }
        
        return true;
    }
};

// Welcome to create a PR to complete the code of this language, thanks!

Dear LeetCoders! For a better LeetCode problem-solving experience, please visit website LeetCode.blog: Dare to claim the best practices of LeetCode solutions! Will save you a lot of time!

Original link: 383. Ransom Note - LeetCode Python/Java/C++/JS/C#/Go/Ruby Solutions.

GitHub repository: leetcode-python-java.