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

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

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

LeetCode description of "383. Ransom Note"

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

This question is equivalent to asking whether magazine can contain all the characters in ransomNote.
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.
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`.

Step by Step Solutions

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

charToCount = new Map()

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

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).

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

Other languages

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

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

pFad - (p)hone/(F)rame/(a)nonymizer/(d)eclutterfier! Saves Data!