C++ use bucket sort to find different between s,t.


  • 0
    X

    first I try to use bit manipulation yet the testing case is really a smart pants... (:3)<)
    then switch to bucket sort and it works. ~(^o^)~ muhaha

    class Solution {
    public:
        bool isAnagram(string s, string t) {
            if(s.length() != t.length()) return false; 
            if(s.length() <= 1) return (s.length()==1) ? (s[0]==t[0]) : true ; 
    
    /*=======================================================================================
        V 1.1 : bucket sort! bcz "You may assume the string contains only lowercase alphabets."
        Time: O(n), space:O(1) 
    *///=====================================================================================
            vector<int> bucketS(26, 0);
            vector<int> bucketT(26, 0);
            for(int i = 0; i < s.length(); i++){
                int idxS = s[i] - 97; //'a'==97
                int idxT = t[i] - 97; 
                bucketS[idxS] += 1;
                bucketT[idxT] += 1; 
            }
            bool valid = true; 
            for(int i = 0; i < 26; i++){
                if(bucketS[i] != bucketT[i]) valid = false; 
            }
            return valid; 
    
    /*=======================================================================================
        V 1.0 : char --> int, then see sum(s)==sum(t)
        Time: O(n), space:O(1)  BUG: "xaaddy","xbbccy", get true yet should be false. !(o_O)#
    *///=====================================================================================
    /*        int findInt = 0, findXOR = 0; 
            for(int i = 0; i < s.length(); i++){
                findInt += s[i] - t[i]; 
                findXOR ^= s[i] ^ t[i]; 
            }
            return (findInt == 0)&&(findXOR == 0); 
    */
        }
    };
    

Log in to reply
 

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