Solutions

1. Sorting

O(nlogn) time | O(n) space

Intuition

We can first sort both of the string and then compare them with each other.

Algorithm

Sort both strings.
Return true if the sorted strings are equal, otherwise return false.

Sort both strings

1 / 3

Code

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

/**
 * @param {string} s
 * @param {string} t
 * @returns {boolean}
 */
var isAnagram = function (s, t) {
  return [...s].sort().join('') === [...t].sort().join('')
}

import java.util.Arrays;

class Solution {
    public boolean isAnagram(String s, String t) {
        char[] first = s.toCharArray();
        char[] second = t.toCharArray();
        Arrays.sort(first);
        Arrays.sort(second);
        return Arrays.equals(first, second);
    }
}

2. Hash Table

O(n) time | O(1) space

Intuition

We can count the characters of each string in its own hash map and then compare the two hash maps.

Algorithm

Count the characters of the first string in a hash map.
Count the characters of the second string in another hash map.
Return true if the two hash maps are equal, otherwise return false.

→

count p

1 / 10

Code

def isAnagram(s: str, t: str) -> bool:
    return counts(s) == counts(t)


def counts(text: str) -> dict[str, int]:
    result = {}
    for c in text:
        result[c] = result.get(c, 0) + 1
    return result

/**
 * @param {string} s
 * @param {string} t
 * @returns {boolean}
 */
var isAnagram = function (s, t) {
  const first = counts(s)
  const second = counts(t)
  if (first.size !== second.size) return false
  for (const [c, n] of first) {
    if (second.get(c) !== n) return false
  }
  return true
}

var counts = function (text) {
  const result = new Map()
  for (const c of text) result.set(c, (result.get(c) ?? 0) + 1)
  return result
}

import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean isAnagram(String s, String t) {
        return counts(s).equals(counts(t));
    }

    private Map<Character, Integer> counts(String text) {
        Map<Character, Integer> result = new HashMap<>();
        for (char c : text.toCharArray()) result.merge(c, 1, Integer::sum);
        return result;
    }
}

The space complexity is O(1) because each hash map contains at most 26 keys, one for every lowercase English letter.