easyArrays & Matrix (Must-Do)

Valid Anagram

Determine whether two lowercase words contain exactly the same letters with the same frequencies.

LeetCode ↗

Work through the cases

3 examples

Input notation

Two nonempty lowercase words on separate lines.

Expected result

true or false.

Case 1

Input

silent
listen

Expected output

true

Case 2

Input

rat
car

Expected output

false

Case 3

Input

a
aa

Expected output

false

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

Anagrams have identical character counts. Unequal lengths fail immediately. Count s, then decrement while scanning t; a negative count means they differ.

We first determine whether the length of the two strings is equal. If they are not equal, the characters in the two strings must be different, so return false.

Otherwise, we use a hash table or an array of length 26 to record the number of times each character appears in the string s, and then traverse the other string t. Each time we traverse a character, we subtract the number of times the corresponding character appears in the hash table by one. If the number of times after subtraction is less than 0, the number of times the character appears in the two strings is different, return false. If after traversing the two strings, all the character counts in the hash table are 0, it means that the characters in the two strings appear the same number of times, return true.

The time complexity is O(n), the space complexity is O(C), where n is the length of the string; and C is the size of the character set, which is C=26 in this problem.

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

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.