Valid Anagram

• LeetCode: Valid Anagram

• Problem:

Given two strings s and t, write a function to determine if t is an anagram of s.

For example,
s = "anagram", t = "nagaram", return true.
s = "rat", t = "car", return false.

• Note:

You may assume the string contains only lowercase alphabets.

• Analysis:

Anagram:

1. both length are equal.

2. the number of every characters are equal.

Therefore,

Use a hashmap to count the number of characters in string s.

And use this hashmap to check whethear strint t is anagram or not.

• Code - Java:

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

• Code - C++:

class Solution {
public:
    bool isAnagram(string s, string t) {
        vector<int> counts(26, 0);
        int lenS = s.length();
        int lenT = t.length();
        if (lenS != lenT) {
            return false;
        }
        for (int i = 0; i < lenS; i++) {
            counts[s[i] - 'a'] += 1;
        }
        for (int i = 0; i < lenT; i++) {
            if (counts[t[i] - 'a'] == 0) {
                return false;
            }
            counts[t[i] - 'a'] -= 1;
        }
        return true;
    }
};

• Code - Python:

class Solution(object):
    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        counts = [0 for i in range(26)]
        lenS, lenT = len(s), len(t)
        if lenS != lenT:
            return False
        for ch in s:
            counts[ord(ch) - ord('a')] += 1
        for ch in t:
            if counts[ord(ch) - ord('a')] == 0:
                return False
            counts[ord(ch) - ord('a')] -= 1
        return True

• Time Complexity: O(N), N is the length of input string s

• Space Complexity: O(N), N is the length of input string s