DEV Community

Daniel Zaltsman
Daniel Zaltsman

Posted on

Valid Anagram

Here we have a new leetcode problem:
Given two strings s and t , write a function to determine if t is an anagram of s.

Let's go over the definition of an anagram: a word, phrase, or sentence formed from another by rearranging its letters:
“Angel” is an anagram of “glean.”

So for a word to an anagram of another, they must use the same letters and also the same amount of letters.

One solution is to compare both strings by turning them into arrays, sorting them, and comparing them one by one. However, this is very slow. The worst case scenario is the time complexity being O(n^2).

Here's my solution:

const isAnagram = (s, t) => {
    if(!s || !t){
       return null
       }
    if(s.length !== t.length){
       return false 
       }

    let obj = {}

    for(let i = 0; i < s.length; i++){
        if(obj[s[i]]){
           obj[s[i]]++
           }
        else{
            obj[s[i]] = 1
        }
    }

    for(let i = 0; i < t.length; i++){
        if(!obj[t[i]]){
           return false
           }
        if(obj[t[i]] === 0){
           return false
           }
        if(obj[t[i]]){
           obj[t[i]]--
           }
    }
    return true
};

Step 1: Take all the letters from the first word and put them into a hash table, the keys being each letter, and the value being how many occurrences of each letter.

Step 2: Run through the second word and run each letter from the second word to the keys of the hash table with three conditions placed in it. The first case tests to see whether the letter is in the object at all, and if it isn't would disqualify it from being an anagram. The second case checks to see if the value of the letter is greater than 0. If it is, that means there is an extra letter occurrence, which means it is not an anagram. The last condition tests to see if it the letter exists in the hash table. To account for that letter, we lowered the value for that letter in the hashtable. Therefore, the case where there are no more letters in the word we are comparing, and all values in the hashmap are 0 is the case where it is a valid anagram.

This solution is O(n) + O(m). I've also put a condition before the main comparison starts to check if the lengths are equal.

Top comments (0)