C++ Two-Pass with explanation


  • 1
    J

    /*
    The definitions of bull and cows.
    Bull: the right character in the right position
    Cow: the right character in the wrong position
    The idea is two pass scanning First pass is to count how many bulls and use a hash_map to track other "right" characters needed. Second pass is to count how many "right" characters (which can be found in the hash map) but in the wrong position
    */

    class Solution {
        public:
            string getHint(string secret, string guess) {
                assert(secret.size()==guess.size());
                int n = secret.size();
                
                unordered_map<char, int> hash;
                int bulls=0, cows=0;
                for(int i =0;i<n;i++){
                    if(secret[i]==guess[i]) bulls++;
                    else hash[secret[i]]++;
                }
         
                for(int i =0;i<n;i++){
                    char cur = guess[i];
                    if(cur!=secret[i] && hash.find(cur)!=hash.end()){
                        cows++;
                        hash[cur]--;
                        if(hash[cur]==0) hash.erase(cur);
                    }
                }
                return to_string(bulls)+"A"+to_string(cows)+"B";
            }
        };

Log in to reply
 

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