Two AC C++ solution, 92 ms and 4 ms.


  • 5

    The basic idea of this problem is calculate Bulls number firstly, then calculate Cows number.
    This is my first solution code:

    string getHint(string s, string g) 
    {
    	if (s.empty())
    		return "0A0B";
    	int i, j, a, b;
    	int sz = s.size();
    	a = b = 0;
    	vector<int> vs(sz, 1);
    	vector<int> vg(sz, 1);
    	for (i = 0; i < sz; ++i)
    	{
    		if (s[i] == g[i])
    		{
    			++a;
    			vs[i] = vg[i] = 0;
    			continue;
    		}
    	}
    	for (i = 0; i < sz; ++i)
    	{
    		if (0 == vs[i])
    			continue;
    		for (j = 0; j < sz; ++j)
    		{
    			if (0 == vg[j] || i == j)
    				continue;
    			if (s[i] == g[j])
    			{
    				++b;
    				vg[j] = 0;
    				break;
    			}
    		}
    	}
    	return to_string(a) + "A" + to_string(b) + "B";
    }
    

    It costs 92 ms.

    The problem also told us character only '0'~'9' be used. Then the code can be improved as follow:

    string getHint(string s, string g)
    {
    	if (s.empty())
    		return "0A0B";
    	int i, j, a, b;
    	int sz = s.size();
    	a = b = 0;
    	vector<int> vs(10, 0);
    	vector<int> vg(10, 0);
    	for (i = 0; i < sz; ++i)
    	{
    		if (s[i] == g[i])
    		{
    			++a;
    			continue;
    		}
    		++vs[s[i] - '0'];
    		++vg[g[i] - '0'];
    	}
    	for (i = 0; i < 10; ++i)
    		b += min(vs[i], vg[i]);
    	return to_string(a) + "A" + to_string(b) + "B";
    }
    

    In the first loop calculate the digits' ('0'~'9') number that didn't paired. In the second loop choose the smaller number means at least these numbers of digits could be paired but at wrong position now.


Log in to reply
 

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