Valid Anagram String Check Algorithms using Hash Table

Given two strings s and t, write a function to determine if t is an anagram of s.

For example,
s = “anagram”, t = “nagaram”, return true.
s = “rat”, t = “car”, return false.

Note:
You may assume the string contains only lowercase alphabets.

Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?

Here is the definition of ‘anagram’:

The result of rearranging the letters of a word or phrase to produce a new word or phrase, using all the original letters exactly once

How to Check if Two Strings are Anagrams?

So, since all letters are lowercase, we can create an array of 26 integers storing the counter of appearance for each letter for the first word. Decrementing the counters for letters in the second word. Finally, we just have to check if all counters are zero. A Non-zero counter would mean that the number of letters used are different.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    bool isAnagram(string s, string t) {
        int c[26] = {0};
        for (int i = 0; i < s.length(); i ++) {
            c[s[i] - 97] ++;
        }
        for (int i = 0; i < t.length(); i ++) {
            c[t[i] - 97] --;
        }
        for (int i = 0; i < 26; i ++) {
            if (c[i] != 0) {
                return false;
            }
        }
        return true;
    }
};

class Solution {
public:
    bool isAnagram(string s, string t) {
        int c[26] = {0};
        for (int i = 0; i < s.length(); i ++) {
            c[s[i] - 97] ++;
        }
        for (int i = 0; i < t.length(); i ++) {
            c[t[i] - 97] --;
        }
        for (int i = 0; i < 26; i ++) {
            if (c[i] != 0) {
                return false;
            }
        }
        return true;
    }
};

If it is a unicode string, you cannot assume that it is a ASCII lowercase (start from 97). However, you can similarly have a STL::map to store the counters. The final step is to iterate the map.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
public:
    bool isAnagram(string s, string t) {
        map<char, int> c;
        for (int i = 0; i < s.length(); i ++) {
            if (c.count(s[i])) {
                c[s[i]] ++;
            } else {
                c[s[i]] = 1;
            }
        }
        for (int i = 0; i < t.length(); i ++) {
            if (c.count(t[i])) {
                c[t[i]] --;
            } else {
                c[t[i]] = 1;
            }
        }
        for (auto p = c.begin(); p != c.end(); ++ p) {
            if (p->second != 0) {
                return false;
            }
        }
        return true;
    }
};

class Solution {
public:
    bool isAnagram(string s, string t) {
        map<char, int> c;
        for (int i = 0; i < s.length(); i ++) {
            if (c.count(s[i])) {
                c[s[i]] ++;
            } else {
                c[s[i]] = 1;
            }
        }
        for (int i = 0; i < t.length(); i ++) {
            if (c.count(t[i])) {
                c[t[i]] --;
            } else {
                c[t[i]] = 1;
            }
        }
        for (auto p = c.begin(); p != c.end(); ++ p) {
            if (p->second != 0) {
                return false;
            }
        }
        return true;
    }
};

Both approaches implement same ideas. Both have O(n) complexity. However, the space complexity for the first approach is O(1) while the second approach uses STL::map (so it depends on how STL::map is implemented).

Using Hash Maps to Store the Character Frequencies

We can use two hash maps e.g. unordered_map to store the character frequencies and then just compare both maps directly:

1
2
3
4
5
6
7
8
9
10

class Solution {
public:
    bool isAnagram(string s, string t) {
        unordered_map<int, int> ss;
        unordered_map<int, int> tt;
        for (auto &n: s) ss[n] ++;
        for (auto &n: t) tt[n] ++;
        return ss == tt;
    }
};

class Solution {
public:
    bool isAnagram(string s, string t) {
        unordered_map<int, int> ss;
        unordered_map<int, int> tt;
        for (auto &n: s) ss[n] ++;
        for (auto &n: t) tt[n] ++;
        return ss == tt;
    }
};

Or even simpler, we can store/count them using unordered_multiset:

1
2
3
4
5
6
7
8

class Solution {
public:
    bool isAnagram(string s, string t) {
        unordered_multiset<char> ss(begin(s), end(s));
        unordered_multiset<char> tt(begin(t), end(t));
        return ss == tt;
    }
};

class Solution {
public:
    bool isAnagram(string s, string t) {
        unordered_multiset<char> ss(begin(s), end(s));
        unordered_multiset<char> tt(begin(t), end(t));
        return ss == tt;
    }
};

–EOF (The Ultimate Computing & Technology Blog) —