My C++ code (12ms, O(1) space, O(N) time)


  • 4
    D

    Use an array as hashtable to count the characters of s and t and see if they match. Here, we use zerocrossing to count the number of zero crossing, if a counter goes from 0 to 1 or -1, we increase zero crossing counter, if a counter goes back to zero, reduce zero crossing counter. If s has the same character set as t, zerocrossing should be 0.

    class Solution {
    public:
        bool isAnagram(string s, string t) {
            int i, sSize = s.size(), tSize = t.size(), zerocrossing = 0, counter[26];
            if(sSize!=tSize) return false;
            for(i=0, fill_n(counter, 26, 0); i<sSize; ++i)
            {
                zerocrossing += ( (++counter[s[i]-'a']==0)?-1:(counter[s[i]-'a']==1) );
                zerocrossing += ( (--counter[t[i]-'a']==0)?-1:(counter[t[i]-'a']==-1) );
            }
            
            return zerocrossing == 0;
        }
    };
    

    You can also do sorting, O(NlogN) time, 76 ms

    class Solution {
    public:
        bool isAnagram(string s, string t) {
            std::sort(s.begin(), s.end());
            std::sort(t.begin(), t.end());
            return s==t;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.