Leetcode Easy

Question 1

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

Answer 1

An anagram is when two words share the same letters at the same frequency but in a different arrangement, like rescue and secure.

There are two ways to solve this problem. Sorting and frequency counting.

Sorting looks like:

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }
    char[] str1 = s.toCharArray();
    char[] str2 = t.toCharArray();
    Arrays.sort(str1);
    Arrays.sort(str2);
    return Arrays.equals(str1, str2);
}

Frequency counting looks like a couple strategies.

Mine:

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        # another way to think of it: same character counts
        if (len(s) != len(t)):
            return False

        scnts = {}
        for i in range(len(s)):
            if s[i] not in scnts:
                scnts[s[i]] = 1
            else:
                scnts[s[i]] += 1
        
        tcnts = {}
        for i in range(len(t)):
            if t[i] not in tcnts:
                tcnts[t[i]] = 1
            else:
                tcnts[t[i]] += 1
        
        return scnts == tcnts

Time O(N), space O(k)

The approved solution takes more caution to use up less space, but gives up on unicode support. This would likely take up more space with unicode, in which case you could use a hashmap like I do.

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }
    int[] table = new int[26];
    for (int i = 0; i < s.length(); i++) {
        table[s.charAt(i) - 'a']++;
    }
    for (int i = 0; i < t.length(); i++) {
        table[t.charAt(i) - 'a']--;
        if (table[t.charAt(i) - 'a'] < 0) {
            return false;
        }
    }
    return true;
}

Time O(N), space O(1)

Using a single map

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if (len(s) != len(t)):
            return False

        cnts = {}
        for i in range(len(s)):
            cnts[s[i]] = cnts.get(s[i], 0) + 1
        
        for i in range(len(t)):
            cnts[t[i]] = cnts.get(t[i], 0) - 1

        for key in cnts.keys():
            if cnts[key] != 0:
                return False
        
        return True