Dare2Solve
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.
Count Characters in magazine
:
Use a dictionary to count the occurrences of each character in magazine
.
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
.
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
.
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)
.
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.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();
}
};
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
for char in magazine:
ransomNote = ransomNote.replace(char, '', 1)
return ransomNote == ''
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
for (char c : magazine.toCharArray()) {
ransomNote = ransomNote.replaceFirst(String.valueOf(c), "");
}
return ransomNote.isEmpty();
}
}
var canConstruct = function (ransomNote, magazine)
{
for (const char of magazine)
{
ransomNote = ransomNote.replace(char, "");
}
if (!ransomNote) return true;
else return false;
};