leetcode Question: Valid Anagram

Valid Anagram

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:

This simple but important problem would provide you some thinking when dealing with quite a lot of programming questions. The first one is to use sorting, while the other is to use map/hashmap/dictionary.

Considering this problem, the definition of anagram requires two string have exactly same type of chars and the same count of the chars.

Therefore, what we need is to compare  the two strings in some ways, so that we can check both the type and the count of the chars in two strings.  Obviously,  find some data structure to save each char would work well. Then it is naturally comes the use of map, which stores the key and value pair in the buffer, and the "check" process takes only O(1) time.  See the code below you will easily find how it works in just several lines of code.

Using a map will definitely open some new spaces to save the key-value pairs. What if we do not use extra space?  In this problem, if we could "move"  the chars of both strings, check if the two strings are same would solve the anagram. One way of "move" chars is to use sort, since sorting chars is unique to every string and will never lose any of the chars (so the count of chars will not change). So, just sort the strings in same order, then a simple comparison will work well. However, it will take more time, where the sorting have O(n log n) complexity.

Code(C++):

class Solution {
public:
    bool isAnagram(string s, string t) {
        
        int mp[26] = {0};
        if (s.size()!= t.size()){return false;}
        for (int i=0;i<s.size();++i){
            mp[s[i]-'a'] += 1;
            mp[t[i]-'a'] -= 1;
        }
        for (int i=0; i< 26;i++){
            if (mp[i] != 0) {return false;}
        }
        return true;
        
        
        //sort(s.begin(),s.end());
        //sort(t.begin(),t.end());
        //return s == t;
    }
};

Code(Python):

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