[
math
string
]
Leetcode 0299. Bulls and Cows
https://leetcode.com/problems/bulls-and-cows
Easy, but interesting problem, because it can be solved in different ways.
- Let us first evaluate number of bulls
B
: by definition it is number of places with the same digit insecret
andguess
: so let us just traverse our strings and count it. - Now, let us evaluate both number of cows and bulls:
B_C
: we need to count each digit insecret
and inguess
and choose the smallest of these two numbers. Evaluate sum for each digit. - Finally, number of cows will be
B_C - B
, so we just return return the answer!
Complexity: both time and space complexity is O(1)
. Imagine, that we have not 4
lengths, but n
, then we have O(n)
time complexity and O(10)
space complexity to keep our counters.
class Solution:
def getHint(self, secret, guess):
B = sum([x==y for x,y in zip(secret, guess)])
Count_sec = Counter(secret)
Count_gue = Counter(guess)
B_C = sum([min(Count_sec[elem], Count_gue[elem]) for elem in Count_sec])
return str(B) + "A" + str(B_C-B) + "B"
If you like the solution, you can upvote it on leetcode discussion section: Problem 0299