Home | Projects | Notes > Problem Solving > LC - E - 242. Valid Anagram (undordered_map)

LC - E - 242. Valid Anagram (undordered_map)

Solutions in C++

Solution 1

This solution uses STL unordered_map container.

Complexity Analysis:

• $T=O(n)$$T = O(n)$ where $n$$n$ is the number of elements in the given string s and t

• $S=O(n)$$S = O(n)$ since the unordered_map of size $n$$n$ is used

Solution:

xxxxxxxxxx
20
1
class Solution {
2
public:
3
    bool isAnagram(string s, string t) {
4
        unordered_map<char, int> m;
5

6
        // add characters of the string s to the map m
7
        for (auto ch : s)
8
            m[ch]++;
9

10
        // remove characters of the string t from the map m
11
        for (auto ch : t)
12
        {
13
            if (--m[ch] == 0)
14
                m.erase(ch);
15
        }
16

17
        // if t is an anagram of s, m will be empty at this point
18
        return m.empty();
19
    }
20
};