Bulls and Cows — LeetCode 299 Python Solution

The problem

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.

Example

Input

secret = "1807", guess = "7810"

Output

"1A3B"

Explanation

Bulls are connected with a '|' and cows are underlined:

Python solution

class Solution:
    def getHint(self, secret: str, guess: str) -> str:
        cnt1, cnt2 = Counter(), Counter()
        x = 0
        for a, b in zip(secret, guess):
            if a == b:
                x += 1
            else:
                cnt1[a] += 1
                cnt2[b] += 1
        y = sum(min(cnt1[c], cnt2[c]) for c in cnt1)
        return f"{x}A{y}B"

Complexity

Pattern: Hash Map

Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 299. Bulls and Cows is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Hash Table and Counting.

The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.

Related problems