Sponsored
Sponsored
This approach involves using hash maps to count the frequency of each letter in both ransomNote and magazine. The idea is to determine if magazine has enough of each letter to build ransomNote.
magazine.ransomNote and check if the magazine frequency is sufficient.ransomNote has a higher frequency than in magazine, return false.true.Time Complexity: O(m + n), where m and n are the lengths of magazine and ransomNote, respectively.
Space Complexity: O(1), as the space is allocated for a fixed-size frequency array.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public bool CanConstruct(string ransomNote, string magazine) {
6 Dictionary<char, int> count = new Dictionary<char, int>();
7 foreach (char c in magazine) {
8 if (count.ContainsKey(c)) count[c]++;
9 else count[c] = 1;
10 }
11 foreach (char c in ransomNote) {
12 if (!count.ContainsKey(c) || count[c] <= 0) return false;
13 count[c]--;
}
return true;
}
}The C# solution uses a dictionary to maintain frequency counts. It checks if ransomNote can be constructed by decrementing counts and verifying that no count drops below zero.
Instead of counting character frequencies, we can sort both ransomNote and magazine and use a two-pointer technique to check if magazine contains all letters needed for ransomNote in a sorted order.
ransomNote and magazine.ransomNote are matched, return true; otherwise, return false.Time Complexity: O(n log n + m log m), dominated by sorting
Space Complexity: O(1)
#include <string>
using namespace std;
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
sort(ransomNote.begin(), ransomNote.end());
sort(magazine.begin(), magazine.end());
int i = 0, j = 0;
while (i < ransomNote.length() && j < magazine.length()) {
if (ransomNote[i] == magazine[j]) {
i++;
}
j++;
}
return i == ransomNote.length();
}
};By sorting both strings, we can use a straightforward two-pointer technique. This approach avoids manual frequency counting and takes advantage of sorted order to verify that every character in ransomNote can be formed using characters from magazine.