Ransom Note Problem


Description

LeetCode Problem 383.

Given two stings ransomNote and magazine, return true if ransomNote can be constructed from magazine and false otherwise.

Each letter in magazine can only be used once in ransomNote.

Example 1:

1
2
Input: ransomNote = "a", magazine = "b"
Output: false

Example 2:

1
2
Input: ransomNote = "aa", magazine = "ab"
Output: false

Example 3:

1
2
Input: ransomNote = "aa", magazine = "aab"
Output: true

Constraints:

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


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int count[26] = {0};
        for(char ch : magazine)
            count[ch - 'a']++;
        
        for(char ch : ransomNote)
            if(count[ch - 'a']-- <= 0)
                return false;
        
        return true;
    }
};




Related Posts

Find Duplicate Subtrees Problem

LeetCode 652. Given the rootof a binary tree, return all...

Delete And Earn Problem

LeetCode 740. You are given an integer array nums. You...

Degree Of An Array Problem

LeetCode 697. Given a non-empty array of non-negative integers nums,...

Custom Sort String Problem

LeetCode 791. You are given two strings order and s....

Basic Calculator IV Problem

LeetCode 770. Given an expression such as expression = “e...

Sort Characters By Frequency Problem

LeetCode 451. Given a string s, sort it in decreasing...