You are playing the Bulls and Cows game with your friend.
You write down a secret number and ask your friend to guess what the number is. When your friend makes a guess, you provide a hint with the following info:
Given the secret number secret and your friend's guess guess, return the hint for your friend's guess.
The hint should be formatted as "xAyB", where x is the number of bulls and y is the number of cows. Note that both secret and guess may contain duplicate digits.
Example 1:
Input: secret = "1807", guess = "7810" Output: "1A3B" Explanation: Bulls are connected with a '|' and cows are underlined: "1807" | "7810"
Example 2:
Input: secret = "1123", guess = "0111" Output: "1A1B" Explanation: Bulls are connected with a '|' and cows are underlined: "1123" "1123" | or | "0111" "0111" Note that only one of the two unmatched 1s is counted as a cow since the non-bull digits can only be rearranged to allow one 1 to be a bull.
Constraints:
1 <= secret.length, guess.length <= 1000secret.length == guess.lengthsecret and guess consist of digits only.
The description was taken from https://leetcode.com/problems/bulls-and-cows/.
#O(N) Time, O(1) Space
class Solution:
def getHint(self, secret: str, guess: str) -> str:
bulls, need = {}, {}
cows = 0
for i in range(len(secret)):
if secret[i] == guess[i]:
bulls[i] = True
else:
if secret[i] in need:
need[secret[i]] += 1
else:
need[secret[i]] = 1
for i, num in enumerate(guess):
if i in bulls:
continue
if num in need:
need[num] -= 1
cows += 1
if need[num] == 0:
del need[num]
return "{}A{}B".format(len(bulls), cows)We're looking for matching values with matching indices for bulls and matching values with nonmatching indices for cows.
What is important to note is for cows, we can only reorder the value once so if we are going to make a list of cows then we will need to decrement it each time we make that reordering.
What we can do is utilize a couple of HashMaps.
We'll make one initial pass through the secret string to look for bulls. We'll check for matching values in matching indices and if we find any, we'll add the corresponding indices to the bulls HashMap. Otherwise, we will add each value that we need which may be fulfilled by cows in our second pass.
Within our second pass, we will now be looking for cows by traversing the guess string. If we find that we have a value that was in the HashMap of values that we need, we will decrement that value and increment our count of cows.
When we have finished our traversal through the guess string, the length of the bulls HashMap and the count of cows will let us know how many of each we have.
Let's start by initializing our bulls and need HashMaps.
bulls, need = {}, {}
Next, we'll initialize our cow count.
cows = 0
For each index in the secret string, we'll see if we have a matching value in the corresponding index of the guess string.
If we do, then we'll add the index to the bulls HashMap so that we know to skip it when we're counting bulls.
for i in range(len(secret)):
if secret[i] == guess[i]:
bulls[i] = True
If we don't then we'll add this to the list of values we need by adding its value to the need dictionary, or incrementing its frequency if it is already there.
else:
if secret[i] in need:
need[secret[i]] += 1
else:
need[secret[i]] = 1
Now let's traverse the guess string.
for i, num in enumerate(guess):
If the current index is a bull then we can't use this value as a cow, so we will continue to the next one.
if i in bulls:
continue
Otherwise, we'll see if the current number is needed for the secret.
If the number is in the need dictionary then we have an inventory that we can use for a cow.
If that's the case then we'll decrement the frequency within the dictionary and increment our count of cows.
if num in need:
need[num] -= 1
cows += 1
Once we do that, however, we'll need to check if that frequency is now zero and delete it so that we don't try to make a false cow from it again later.
if need[num] == 0:
del need[num]
Now that we have our count of bulls and cows, we'll return that count in the required format.
return "{}A{}B".format(len(bulls), cows)