Leetcode Problem 242: Valid Anagram

Problem description:

Given two strings s and t, return true if t is an anagram of s, and false otherwise. An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Python solution Link to heading


# I like this solution because it uses "Python magic" to measure true 
# equality of values in two different objects, or more specifically it 
# considers the two objects equal so long they point to the same memory
# address. Which is cool, but in a language like Javascript that has 
# no such built-in convenience operator, we'll have to create such 
# comparator function (see Javascript implementation)

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
         n = len(s)
         m = len(t)
         s_occurrences = {}
         t_occurrences = {}

         for i in range(0, n):
            s_occurrences[s[i]] = s_occurrences.get(s[i], 0) + 1

         for i in range(0, m):
            t_occurrences[t[i]] = t_occurrences.get(t[i], 0) + 1

         if s_occurrences == t_occurrences:
             return True
         
         return False

Javascript solution Link to heading


/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}

 */
var isAnagram = function(s, t) {
    var n = s.length;
    var m = t.length;
    var s_occurrences = {};
    var t_occurrences = {};

    for (let i=0; i < n; i++) {
        s_occurrences[s[i]] = (s_occurrences[s[i]] || 0) + 1
    }

    for (let i=0; i < m; i++) {
        t_occurrences[t[i]] = (t_occurrences[t[i]] || 0) + 1
    }

    return object_comparator(s_occurrences, t_occurrences)
};

function object_comparator(a, b) {
    const n = Object.keys(a).length;
    const m = Object.keys(b).length;

    // if the two maps are not of same length then they can't be equal
    if (n !== m) {
        return false
    }

    for(key in a) {
        if(b[key] !== a[key] || b[key] === undefined && !b[key]) {
            return false
        }
    }

    // if we got here then the two objects have identical values and hence "equal"
    return true
}
Python statistics Link to heading
Runtime: 72 ms - beats 43.17 % of python3 submissions
Memory Usage: 14.4 MB -- beats 67.87 % of python3 submissions
Javascript statistics Link to heading
Runtime: 99 ms -- beats 65.12 % of javascript submissions.
Memory Usage: 42.8 MB -- beats 87.29 % of javascript submissions.
Complexity analysis Link to heading

  • Time: $ O(n) ~or~ O(m) $, whichever is bigger between $ n $ or $ m $ since the for loops are not nested. If $ n = m $ then it’s $ O(n + m) = O(2n) = O(n) $

  • Space: $ O(n + m) $ since the size of the two maps created depend on the size of the two input string’s length. $ O(n) $ is also correct when $ n = m $, or when $ n $ dominates $ m $, or vice versa.



Share on:
LinkedIn