299. Bulls and Cows

Problem Statement

link: LeetCode.cn LeetCode

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. When your friend makes a guess, you provide a hint with the following info:

The number of “bulls”, which are digits in the guess that are in the correct position. The number of “cows”, which are digits in the guess that are in your secret number but are located in the wrong position. Specifically, the non-bull digits in the guess that could be rearranged such that they become bulls. Given the secret number secret and your friend’s guess guess, return the hint for your friend’s guess.

The hint should be formatted as “xAyB”, where x is the number of bulls and y is the number of cows. Note that both secret and guess may contain duplicate digits.

Example:

Input: secret = "1807", guess = "7810" Output: "1A3B"

Input: secret = "1123", guess = "0111" Output: "1A1B"

Solution Approach

This solution utilizes a hash table to count the occurrences of digits in both the secret and guess numbers, calculating the number of bulls and cows accordingly.

Algorithm

1. Create two defaultdicts, s_map and g_map, to store the count of each digit in the secret and guess numbers, respectively.
2. Iterate through both secret and guess simultaneously using zip, counting the number of bulls (correctly guessed digits in correct positions) and updating s_map and g_map for the remaining digits.
3. For each digit in s_map, check if it exists in g_map. If it does, add the minimum count of occurrences of the digit in both maps to the count of cows (correctly guessed digits in incorrect positions).

Implement

    class Solution:
    def getHint(self, secret: str, guess: str) -> str:
      s_map = defaultdict(int)
      g_map = defaultdict(int)
      A = B = 0
      for (x, y) in zip(secret, guess):
          if x == y:
              A += 1
          else:
              s_map[x] += 1
              g_map[y] += 1
      for k in s_map:
          if k in g_map:
              B += min(s_map[k], g_map[k])
      return f"{A}A{B}B"
    
       

    
    

Twitter  facebook  Email