242. Valid Anagram

Problem

Solution

Hashmap - O(n) time - O(1) space

The reason this is O(1) space instead of O(n) is the dictionary will only store alphabets. So at most it will store 26 locations so the real space complexity is O(26), which reduces to O(1).

class Solution {
public:
    bool isAnagram(string s, string t) {
        unordered_map<char, int> letters;
        for (char c : s) {
            letters[c]++;
        }
        for (char c : t) {
            if (letters[c] <= 0) return false;
            letters[c]--;
        }
        for (auto item : letters) {
            if (item.second != 0) return false;
        }
        return true;
    }
};

We can improve runtime for this by merging first two loops. Also useful to add an initial check on string lengths. This code means that some of the dictionary items will be negatives at times but that doesn’t matter in the interim loop.

class Solution {
public:
    bool isAnagram(string s, string t) {
        unordered_map<char, int> letters;
        if (s.length() != t.length()) return false;
        for (int i = 0; i < s.length(); i++) {
            letters[s[i]]++;
            letters[t[i]]--;
        }
        for (auto item : letters) {
            if (item.second != 0) return false;
        }
        return true;
    }
};