Solution 1 - Counting (Hash Map)

Count character frequencies in both strings and compare.

TimeComplexity: O(n)

SpaceComplexity: O(k)

""" 0242.1 - Valid Anagram - Solution 1 - Counting (Hash Map) """

from collections import Counter

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return Counter(s) == Counter(t)

if __name__ == "__main__":
    assert Solution().isAnagram("anagram", "nagaram")
    assert not Solution().isAnagram("rat", "car")

function isAnagram(s,t){
 if(s.length!==t.length) return false;
 const m=new Map();
 for(const c of s) m.set(c,(m.get(c)||0)+1);
 for(const c of t){
  if(!m.has(c)) return false;
  m.set(c,m.get(c)-1);
  if(m.get(c)===0) m.delete(c);
 }
 return m.size===0;
}
console.log(isAnagram("anagram","nagaram"));

function isAnagram(s:string,t:string):boolean{
 if(s.length!==t.length) return false;
 const m:Map<string,number>=new Map();
 for(const c of s) m.set(c,(m.get(c)??0)+1);
 for(const c of t){
  const v=m.get(c);
  if(v===undefined) return false;
  if(v===1) m.delete(c); else m.set(c,v-1);
 }
 return m.size===0;
}
console.log(isAnagram("anagram","nagaram"));

package main

func isAnagram(s, t string) bool {
	if len(s) != len(t) {
		return false
	}
	m := map[byte]int{}
	for i := 0; i < len(s); i++ {
		m[s[i]]++
		m[t[i]]--
	}
	for _, v := range m {
		if v != 0 {
			return false
		}
	}
	return true
}

func main() {}

use std::collections::HashMap;

fn is_anagram(s: &str, t: &str) -> bool {
	if s.len() != t.len() { return false; }
	let mut m: HashMap<u8, i32> = HashMap::new();
	for (&a, &b) in s.as_bytes().iter().zip(t.as_bytes().iter()) {
		*m.entry(a).or_insert(0) += 1;
		*m.entry(b).or_insert(0) -= 1;
	}
	m.values().all(|&v| v == 0)
}

fn main() {}

Solution 2 - Sorting

Sort both strings and compare the results.

TimeComplexity: O(n \log n)

SpaceComplexity: O(n)

""" 0242.2 - Valid Anagram - Solution 2 - Sorting """

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return sorted(s) == sorted(t)

if __name__ == "__main__":
    assert Solution().isAnagram("anagram", "nagaram")

package main

import "sort"

func isAnagramSort(s, t string) bool {
	if len(s) != len(t) {
		return false
	}
	a := []byte(s)
	b := []byte(t)
	sort.Slice(a, func(i, j int) bool { return a[i] < a[j] })
	sort.Slice(b, func(i, j int) bool { return b[i] < b[j] })
	for i := range a {
		if a[i] != b[i] {
			return false
		}
	}
	return true
}

func main() {}

0242 - Valid Anagram

Solution 1 - Counting (Hash Map)

Solution 2 - Sorting