What is the core approach to solving the Bulls and Cows problem?

The core approach to solving Bulls and Cows is using hash tables to efficiently count and match digits in both the secret and guess strings.

How do bulls and cows differ in the context of this problem?

Bulls are digits that match both in value and position between the secret and guess, while cows are digits that match in value but are in the wrong position.

Why is using a hash table critical in this problem?

A hash table allows for efficient counting of digit frequencies, which is essential for accurately counting cows while keeping the time complexity manageable.

How do you handle repeated digits when calculating cows?

When handling repeated digits, ensure that cows are counted only for unmatched digits that are available in the secret. Be mindful of the number of occurrences in both strings to avoid overcounting.

What is the expected time complexity for solving Bulls and Cows?

The expected time complexity is O(n), where n is the length of the strings, as we process each character once to count bulls and cows.

#299

Medium

auto_awesome哈希·表·结合·string

LeetCode 题解工作台

猜数字游戏

你在和朋友一起玩猜数字（Bulls and Cows）游戏，该游戏规则如下：写出一个秘密数字，并请朋友猜这个数字是多少。朋友每猜测一次，你就会给他一个包含下述信息的提示：猜测数字中有多少位属于数字和确切位置都猜对了（称为 "Bulls"，公牛），有多少位属于数字猜对了但是位置不对（称为 "…

哈希表字符串计数

题目描述

你在和朋友一起玩猜数字（Bulls and Cows）游戏，该游戏规则如下：

写出一个秘密数字，并请朋友猜这个数字是多少。朋友每猜测一次，你就会给他一个包含下述信息的提示：

猜测数字中有多少位属于数字和确切位置都猜对了（称为 "Bulls"，公牛），
有多少位属于数字猜对了但是位置不对（称为 "Cows"，奶牛）。也就是说，这次猜测中有多少位非公牛数字可以通过重新排列转换成公牛数字。

给你一个秘密数字 secret 和朋友猜测的数字 guess ，请你返回对朋友这次猜测的提示。

提示的格式为 "xAyB" ，x 是公牛个数， y 是奶牛个数，A 表示公牛，B 表示奶牛。

请注意秘密数字和朋友猜测的数字都可能含有重复数字。

示例 1：

输入：secret = "1807", guess = "7810"
输出："1A3B"
解释：数字和位置都对（公牛）用 '|' 连接，数字猜对位置不对（奶牛）的采用斜体加粗标识。
"1807"
  |
"7810"

示例 2：

输入：secret = "1123", guess = "0111"
输出："1A1B"
解释：数字和位置都对（公牛）用 '|' 连接，数字猜对位置不对（奶牛）的采用斜体加粗标识。
"1123"        "1123"
  |      or     |
"0111"        "0111"
注意，两个不匹配的 1 中，只有一个会算作奶牛（数字猜对位置不对）。通过重新排列非公牛数字，其中仅有一个 1 可以成为公牛数字。

提示：

1 <= secret.length, guess.length <= 1000
secret.length == guess.length
secret 和 guess 仅由数字组成

lightbulb

解题思路

方法一：计数

我们创建两个计数器 $cnt1$ 和 $cnt2$ ，分别用来统计秘密数字和朋友猜测的数字中每个数字出现的次数。同时，我们创建一个变量 $x$ 来统计公牛的数量。

然后我们遍历秘密数字和朋友猜测的数字，如果当前数字相同，我们就将 $x$ 加一。否则，我们分别将秘密数字和朋友猜测的数字中的当前数字的计数加一。

最后，我们遍历 $cnt1$ 中的每个数字，取 $cnt1$ 和 $cnt2$ 中当前数字的计数的最小值，然后将这个最小值加到变量 $y$ 中。

最后，我们返回 $x$ 和 $y$ 的值。

1

2

3

4

5

6

7

8

9

10

11

12

13

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"

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Does the candidate consider both bulls and cows efficiently?
question_mark
How well does the candidate handle edge cases like repeated digits in both secret and guess?
question_mark
Can the candidate discuss time and space complexities clearly in relation to hash tables?

warning

常见陷阱

外企场景

error
Failing to properly account for repeated digits can lead to incorrect cow counts.
error
Using a brute force approach for comparing all digits without using a hash table can significantly increase time complexity.
error
Not handling edge cases like when all digits are bulls or cows could result in missed cases.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider a version where the strings have different lengths, adding a validation step before proceeding.
arrow_right_alt
Modify the problem to work with non-digit strings, such as alphanumeric characters.
arrow_right_alt
Incorporate a timing constraint to optimize the solution's performance under time limits.

help

常见问题

外企场景

继续练习

#383 赎金信 #387 字符串中的第一个唯一字符 #451 根据字符出现频率排序