You are playing the following Bulls and Cows game with your friend: You write down a number and ask your friend to guess what the number is. Each time your friend makes a guess, you provide a hint that indicates how many digits in said guess match your secret number exactly in both digit and position (called “bulls”) and how many digits match the secret number but locate in the wrong position (called “cows”). Your friend will use successive guesses and hints to eventually derive the secret number.
Write a function to return a hint according to the secret number and friend’s guess, use
A to indicate the bulls and
B to indicate the cows.
Please note that both secret number and friend’s guess may contain duplicate digits.
Input: secret = "1807", guess = "7810" Output: "1A3B" Explanation:
3cows. The bull is
8, the cows are
Input: secret = "1123", guess = "0111" Output: "1A1B" Explanation: The 1st
1in friend's guess is a bull, the 2nd or 3rd
1is a cow.
Note: You may assume that the secret number and your friend’s guess only contain digits, and their lengths are always equal.
We look at the rules of bulls and cows separately. We need to compare the digits in string secret and string guess.
First, we look at how to calculate bulls. We can transform the two string into two character arrays. Then we compare the digits one by one. When we meet the same digits in the two arrays at the same position, we add bull by one. But note every time we find a match, we need to use ‘.’ to replace it in string secret and string guess to avoid to repeat count them in the cows’ calculating process.
Then we look at how to count cows. First, we put the remain digits in string secret into a HashSet. We use the remain digits in string guess to compare, find a match, we add one to cows. Code:
After we get bulls and cows, the output is easy:
To see more hashtable related problems, see
Problems and Solutions of Hashmap.