September LeetCoding Challenge, Day 10: Bulls and Cows
September 13, 2020The problem for September 10 is Bulls and Cows. You have to return the hint for an opponent’s guess in a game of Bulls and Cows, the paper and pencil game that predated Mastermind.
To get the number of bulls, we simply count the number of digits that match in both digit and position. For the remaining of digits, for each possible digit value, we count the number of times there’s a repeated occurrence in both the guess and the secret. The following is an implementation of this idea:
class Solution {
public:
string getHint(string secret, string guess) {
int N = secret.size();
int bulls = 0, cows = 0;
map<char, int> in_secret, in_guess;
for (int i = 0; i < N; ++i) {
if (secret[i] == guess[i])
bulls++;
else {
in_secret[secret[i]]++;
in_guess[guess[i]]++;
}
}
for (auto itr = in_guess.begin(); itr != in_guess.end(); ++itr) {
char ch = itr->first;
int cnt = itr->second;
cows += min(cnt, in_secret[ch]);
}
ostringstream ss;
ss << bulls << "A" << cows << "B";
return ss.str();
}
};