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.
1#include <stdbool.h>
2#include <string.h>
3
4bool canConstruct(char * ransomNote, char * magazine) {
5 int countThe solution uses an array count of size 26 to store the frequency of each character from 'a' to 'z'. It first increments the counts based on the characters in magazine and then decrements the respective counts as it encounters each character in ransomNote. If any count goes negative, it indicates that ransomNote cannot be formed, hence returning false.
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)
This Java solution uses arrays to hold character data for sorting. The two-pointer approach checks characters in sorted order, allowing us to confirm if ransomNote can be derived from magazine.