Home | Projects | Notes > Problem Solving > LC - E - 383. Ransom Note (map)

LC - E - 383. Ransom Note (map)

Solutions in C

Solution 1

This solution uses C implementation of map using array.

Complexity Analysis:

• $T=O(n)$$T = O(n)$ where $n$$n$ is the length of the given string magazine

• $S=O(1)$$S = O(1)$ since a constant-size array (map) is used

Solution:

xxxxxxxxxx
25
1
#define MAX 26
2

3
bool canConstruct(char * ransomNote, char * magazine){
4
    int map[MAX] = {0};
5
    int i, idx;
6

7
    // insert characters in 'magazine' into 'map'
8
    for (i = 0; i < strlen(magazine); i++)
9
    {
10
        idx = magazine[i] - 'a';
11
        map[idx]++;
12
    }
13

14
    // consume letters in 'ransomNote' from 'map'
15
    for (i = 0; i < strlen(ransomNote); i++)
16
    {
17
        idx = ransomNote[i] - 'a';
18

19
        // if cannot consume, return false
20
        if (map[idx]-- == 0)
21
            return false;
22
    }
23

24
    return true; 
25
}