[C++] 4ms Straight forward solution two pass O(N) time


  • 41
    M

    The idea is simple, if two char is match, add aCnt, otherwise, record it and process bCnt in second pass.

    class Solution {
    public:
        // only contains digits 
        string getHint(string secret, string guess) {
            int aCnt = 0;
            int bCnt = 0;
            vector<int> sVec(10, 0); // 0 ~ 9 for secret
            vector<int> gVec(10, 0); // 0 ~ 9 for guess 
            if (secret.size() != guess.size() || secret.empty()) { return "0A0B"; }
            for (int i = 0; i < secret.size(); ++i) {
                char c1 = secret[i]; char c2 = guess[i];
                if (c1 == c2) {
                    ++aCnt; 
                } else {
                    ++sVec[c1-'0'];
                    ++gVec[c2-'0'];
                }
            }
            // count b 
            for (int i = 0; i < sVec.size(); ++i) {
                bCnt += min(sVec[i], gVec[i]);
            }
            return to_string(aCnt) + 'A' + to_string(bCnt) + 'B';
        }
    };

  • -3
    M

    Java version:

    public String getHint(String secret, String guess) 
    {
        int len = secret.length();
        int nCows = 0;
        int nBull = 0;
        int[] diffS = new int[10];
        int[] diffG = new int[10];
        for(int i=0; i<len; ++i)
        {
            if(guess.charAt(i) == secret.charAt(i)) ++nBull;
            else
            {
                ++diffS[secret.charAt(i) - '0'];
                ++diffG[guess.charAt(i) - '0'];
            }
        }
        
        for(int i=0; i<10; ++i)
        {
            nCows += Math.min(diffS[i], diffG[i]);
        }
        
        return "" + nBull + "A" + nCows + "B";
    }
    

  • 0
    D

    Excuse me. Can you provide more explanation about your codes. For example, what is the function of
    ++sVec[c1-'0'];
    ++gVec[c2-'0'];
    and bCnt += min(sVec[i], gVec[i]);
    Thank you


  • 0

    Nice solution!!! Very smart idea to count the cow. Count the number of unpaired digits, and the less one is the cow number. Thank you very much.


  • 1

    ++sVec[c1-'0']; ++gVec[c2-'0']; is used to count digits' (0~9) number which are not paired. bCnt += min(sVec[i], gVec[i]); for example, sVec[1] =2, gVec[1] =3, means there are 2 '1' in secret and 3 '1' in guess can not find paired one, then at least there are 2 '1' is in the wrong place.


  • 0
    Z
    This post is deleted!

  • 0
    Z

    You took advantage of “only digits”. With no use of hash map, your program is definitely fast.


  • -1
    X

    The same as i thought. However, a bit difference appears in the count of cows. My solution is:
    class Solution {
    public:
    string getHint(string secret, string guess) {
    int cntA = 0, cntB = 0;
    int tab[10] = {0};
    string strTmp;
    for (int i = 0; i != guess.size(); ++i) {
    if (guess[i] == secret[i])
    ++cntA;
    else {
    ++tab[secret[i] - '0'];
    strTmp.push_back(guess[i]);
    }
    }
    for (const char & c : strTmp) {
    int & nTmp = tab[c - '0'];
    if (nTmp) {
    --nTmp;
    ++cntB;
    }
    }
    stringstream s;
    s << cntA << "A" << cntB << "B";
    return s.str();
    }
    };
    This one also achieve a 4ms process time.


  • 0
    D

    Mine is similar to yours.

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

  • 0
    U
    string getHint(string secret, string guess) {
            int m[10] = {0}, len = secret.size();
            int A = 0, B = 0;
    
            for(int i=0; i<len; i++) {
                m[secret[i]-'0']++;
                if(secret[i] == guess[i]) A++;
            }
            
            for(int i=0; i<len; i++) {
                if(m[guess[i]-'0'] > 0) B++;
                m[guess[i]-'0']--;
            }
            
            return to_string(A)+"A"+to_string(B-A)+"B";
        }
    

  • 0
    L

    Nice solution! It is easy and concise, In my solution, I use two unordered_map ,also solve the problem. But it is complex!

     
    class Solution {
    public:
    	string getHint(string secret, string guess) {
    		int len = secret.length();
    		unordered_map<int, int> m;//key represents the number,value represents the times of the number appearing
    		unordered_map<int, int> mm;
    		int bull = 0, cow = 0;
    		string res = "";
    		for (int i = 0; i<len; i++)
    		{
    			if (secret[i] == guess[i])//cow number
    				bull++;
    			else
    			{
    				m[secret[i] - '0']++;
    				mm[guess[i] - '0']++;
    			}	
    		}
    		for (int i = 0; i<len; i++)
    		{
    			if (m.find(guess[i] - '0') != m.end())//m has the number
    			{
    				if (mm[guess[i] - '0']>0&&m[guess[i] - '0']>0)
    				{
    					cow++;
    					mm[guess[i] - '0']--;
    					m[guess[i] - '0']--;
    				}
    			}
    		}
    		res = to_string(bull) + "A" + to_string(cow) + "B";
    		return res;
    	}
    };
    

Log in to reply
 

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