Leetcode # 299. Bulls and Cows

https://leetcode.com/problems/bulls-and-cows/

First Solution

Time Complexity: O(len(secret))
Space Complexity: O(len(secret))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def getHint(self, secret: str, guess: str) -> str:
    c_in_secret = collections.defaultdict(set)
    c_in_guess = collections.defaultdict(set)
    for i, c in enumerate(secret):
      c_in_secret[c].add(i)
    A = B = 0
    for i, c in enumerate(guess):
      if c in c_in_secret:
        if i in c_in_secret[c]:
          A += 1
          c_in_secret[c].remove(i)
        else:
          c_in_guess[c].add(i)
    for c in c_in_guess:
      B += min(len(c_in_secret[c]), len(c_in_guess[c]))
    return f"{A}A{B}B"

Better Solution

Time Complexity: O(len(secret))
Space Complexity: O(1)
(The input and output generally do not count towards the space complexity.)

If so far

1. guess contains more s characters than secret: h[s] < 0
   (至目前為止 guess 還有未計算過的 s )
2. secret contains more g characters than guess: h[g] > 0
   (至目前為止 secret 還有未計算過的 g )

then B += 1

※ $$ int(expression) = \begin{cases} 0 & , \text{if expression is } False \\ 1 & , \text{if expression is } True \end{cases} $$

class Solution:
  def getHint(self, secret: str, guess: str) -> str:
    h = collections.defaultdict(int)
    A = B = 0

    for i, s in enumerate(secret):
      g = guess[i]
      if s == g: 
        A += 1
      else:
        B += int(h[s] < 0) + int(h[g] > 0)
        h[s] += 1 # secret has a non-maching character s
        h[g] -= 1 # guess has a non-maching character g
                
    return f"{A}A{B}B"

Last Updated on 2023/08/16 by A1go