MediumNo. 0299
Bulls and Cows — LeetCode 299 Python Solution
- Pattern
- Hash Map
- Topics
- Hash Table, String, Counting
- Reading time
- 2 min
- Source
- leetcode.com
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
- Time
- O(n), where n is the length of the secret number and the friend's guess
- Space · auxiliary
- O(|Σ|), where |Σ| is the size of the character set
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
| No. | Problem | Difficulty |
|---|---|---|
| 0383 | Ransom Note | Easy |
| 0387 | First Unique Character in a String | Easy |
| 0451 | Sort Characters By Frequency | Medium |
| 0692 | Top K Frequent Words | Medium |
| 0767 | Reorganize String | Medium |
| 0811 | Subdomain Visit Count | Medium |
Frequently asked questions
- How hard is LeetCode 299. Bulls and Cows?
LeetCode 299. Bulls and Cows is rated Medium on LeetCode.
- What is the time complexity of LeetCode 299. Bulls and Cows?
The Python solution on this page runs in O(n), where n is the length of the secret number and the friend's guess.
- What is the space complexity of LeetCode 299. Bulls and Cows?
The Python solution on this page uses O(|Σ|), where |\Sigma| is the size of the character set auxiliary space.
- What topics does LeetCode 299. Bulls and Cows cover?
LeetCode 299. Bulls and Cows is tagged Hash Table, String and Counting on LeetCode.