Fuck LeetCode  >  Hash Table  >  383. Ransom Note  >  Solved in Java, Python, JavaScript, C#, Ruby, Go, C++  >  Repost or Contribute

    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.

    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 <= 10^5
    • ransomNote and magazine consist of lowercase English letters.

    Intuition
    PreviousNext

    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.

    Steps

    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

    Complexity

    Time complexity

    O(N)

    Space complexity

    O(N)

    Solution in languages: Java Python JavaScript C# Ruby Go C++

    Java # 

    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;
    }
}

    Python # 

    # 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

    JavaScript # 

    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
};

    C# # 

    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;
    }
}

    Ruby # 

    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

    Go # 

    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
}

    C++ # 

    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;
    }
};
    Solution in languages: Java Python JavaScript C# Ruby Go C++

    Other languages

    Welcome to contribute code to our GitHub repository, thanks! The location of this solution is 383. Ransom Note.
    PreviousNext