Leetcode 242. Valid Anagram

I want to document my thought process on this Leetcode question, https://leetcode.com/problems/valid-anagram/.

First I'll try get an idea of what the function signature should be like while listening to the question. Then I'll start ask clarifying questions and come up with examples. After clarifying, I'll brainstorm some ideas to solve the problem. I want to try throwing different data structures at the problem for now, some may just be for the sake of considering them.

Function signature:

boolean isAnagram(String s, String t)

Clarifying Questions / Assumptions:

Input: null/empty? Any chars to ignore? Upper/lowercase?
Output: How to handle null/length==0?
Assume: no ignored chars, case sensitive

Examples:

s="aba", t="aab" // is anagram
s="abc", t="bab" // not anagram
s="a", t="aa" // diff length
s="", t=null // invalid

Brainstorm:

If string length is different, it is not an anagram. So after we check for this first, we only need to consider same length strings.

What would I do if I had to solve this in real life with paper and pen?

If I were given two sort strings, I would go through every char in string s and look for a match in string t and cross it out when found.
If I were given two whole paragraphs, I would probably need to count the character frequencies and then compare.

(n = s.length)

2 for loops + boolean[] isUsed
- For every char in s, search through t for the same char, and mark the position as used. If we can reach the end of the for loop, then it is a anagram.
- time O(n^2)
  space O(n)
Sort first, then check if both strings are equal
- time O(nlogn) ~ O(n^2) for quicksort
  space O(n) for checking if strings are equal, and quicksort worst case
Counting frequency
- Count frequency of all the chars in string s and store in HashMap<Character, Integer>. Go through all chars in string t, and decrement the count in HashMap. If we can reach the end of string t without the count dropping below 0, then it is a anagram.
- A simpler implementation would be to count frequency of both strings, then check if the numbers match.
- If the chars are within a specific range, we can use int[] instead of HashMap to store the frequency.
- time O(n)
  space O(n)

Code:

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;

        int[] count = countChars(s);
        for (char c : t.toCharArray()) {
            if (count[c - 'a'] == 0) return false;
            count[c - 'a']--;
        }
        return true;
    }

    private int[] countChars(String s) {
        int[] count = new int[26];
        for (char c : s.toCharArray()) {
            count[c - 'a']++;
        }
        return count;
    }
}

Let me know if there is anything I should have considered, or has an error! I'm happy to get any feedback.

Blood Runs Code's Blog

Blood Runs Code's Blog

Leetcode 242. Valid Anagram