LeetCode 299: Bulls and Cows Solution
Master LeetCode problem 299 (Bulls and Cows), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
299. Bulls and Cows
Problem Explanation
Explanation
To solve this problem, we can iterate through the secret and guess strings simultaneously and count the bulls and cows based on the matching digits. While counting the bulls, we mark the positions of those digits to avoid counting them as cows later. For counting cows, we use a hashmap to store the frequency of digits in the secret. We decrement the frequency for each digit that matches in the guess string. If the frequency is greater than 0, it means that digit is a cow. Finally, we construct the result string in the format "xAyB" where x is the number of bulls and y is the number of cows.
- Initialize variables to count bulls, cows, and a hashmap to store the frequency of digits in secret.
- Iterate through the strings secret and guess simultaneously.
- If the digits at the same index are the same, increment the bulls count and mark the position.
- Otherwise, increment the frequency of the digit in secret in the hashmap.
- Iterate through the guess string.
- If the digit is in the hashmap and its frequency is greater than 0, increment cows count and decrement the frequency.
- Construct the result string and return.
Time Complexity: O(n) where n is the length of the input strings (secret and guess). Space Complexity: O(1) due to the constant size of the hashmap storing digit frequencies.
Solution Code
class Solution {
public String getHint(String secret, String guess) {
int bulls = 0, cows = 0;
int[] digits = new int[10];
for (int i = 0; i < secret.length(); i++) {
if (secret.charAt(i) == guess.charAt(i)) {
bulls++;
} else {
digits[secret.charAt(i) - '0']++;
}
}
for (int i = 0; i < guess.length(); i++) {
if (secret.charAt(i) != guess.charAt(i) && digits[guess.charAt(i) - '0'] > 0) {
cows++;
digits[guess.charAt(i) - '0']--;
}
}
return bulls + "A" + cows + "B";
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 299 (Bulls and Cows)?
This page provides optimized solutions for LeetCode problem 299 (Bulls and Cows) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 299 (Bulls and Cows)?
The time complexity for LeetCode 299 (Bulls and Cows) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 299 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 299 in Java, C++, or Python.