383. Ransom Note

Intuition

The problem requires determining if we can construct the ransomNote string using the letters available in the magazine string. Each letter in the magazine can only be used once. This means we need to ensure that for each character in ransomNote, there is a corresponding character in magazine that hasn't been used already.

Approach

1. Count Characters in magazine: Use a dictionary to count the occurrences of each character in magazine.
2. Check Characters in ransomNote: Iterate through each character in ransomNote and check if it is present in the dictionary with a non-zero count. - If the character is present and its count is greater than zero, decrement the count. - If the character is not present or its count is zero, return false.
3. Return true: If all characters in ransomNote can be matched with characters in magazine, return true.

This approach ensures that we efficiently check the availability of each character in ransomNote against magazine.

Complexity

Time Complexity

• Counting characters in magazine takes O(m) time, where m is the length of magazine.
• Checking each character in ransomNote takes O(n) time, where n is the length of ransomNote.
• Overall time complexity is O(m + n).

Space Complexity

• The space complexity is O(1) since the dictionary will hold at most 26 key-value pairs if we consider only lowercase English letters. This can be considered constant space.

Code

C++

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        for (char c : magazine) {
            size_t pos = ransomNote.find(c);
            if (pos != string::npos) {
                ransomNote.erase(pos, 1);
            }
        }
        return ransomNote.empty();
    }
};

Python

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        for char in magazine:
            ransomNote = ransomNote.replace(char, '', 1)
        return ransomNote == ''

Java

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        for (char c : magazine.toCharArray()) {
            ransomNote = ransomNote.replaceFirst(String.valueOf(c), "");
        }
        return ransomNote.isEmpty();
    }
}

JavaScript

var canConstruct = function (ransomNote, magazine)
{
    for (const char of magazine) 
    {
        ransomNote = ransomNote.replace(char, "");
    }
    if (!ransomNote) return true;
    else return false;
};