242. Valid Anagram

Description of the Problem

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

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: s = "anagram", t = "nagaram"
Output: true

Example 2:

Input: s = "rat", t = "car"
Output: false

Constraints:

1 <= s.length, t.length <= 5 * 10^4
s and t consist of lowercase English letters.

Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?

Solution

Explanation

The key of the problem is to count the occurences of each charaters of each string and to see whether the counts is equal or not.

Answer to followup question: char in Rust already handles the case of UTF-8. Therefore, the following code meet the requirement of follow-up question.

Code (Rust)

impl Solution {
    pub fn is_anagram(s: String, t: String) -> bool {
        use std::collections::HashMap;

        let mut bucket = HashMap::new();

        for c in s.chars() {
            if let Some(count) = bucket.get_mut(&c) {
                *count += 1;
            }else{
                bucket.insert(c, 1);
            }
        }

        for c in t.chars() {
            if let Some(count) = bucket.get_mut(&c) {
                *count -= 1;
                if *count == 0 {
                       bucket.remove(&c);
                }
            }else{
                return false;
            }
        }

        return bucket.len() == 0;
    }
}

Code (Rust) - Alternative

impl Solution {
    pub fn is_anagram(s: String, t: String) -> bool {
        let mut s : Vec<char> = s.chars().collect();
        let mut t : Vec<char> = t.chars().collect();
        s.sort();
        t.sort();

        return s==t;
    }
}

Complexity

m is the length of string s
n is the length of string t

Time complexity:

\( T(n) = O(\max(m,n)) \)

Auxiliary Space:

\( S(n) = O(\max(m,n)) \)
- For HashMap

Leetbook