unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 299: Bulls and Cows

link

If secret[i] = guess[i] that is a bull. So, we can process and exclude bull positions. In the remaining positions if guess[i] could be matched with a secret[j], that is a cow. So, we use two passes: (1) Bull pass (2) Cow pass.

Time \mathcal{O}(n), space: \mathcal{O}(n).

class Solution:
    def getHint(self, secret: str, guess: str) -> str:
        secret_map = {}
        for c in secret:
            secret_map[c] = secret_map.get(c, 0) + 1

        bulls = set()
        for i, pair in enumerate(zip(secret, guess)):
            s, g = pair
            if s == g:
                secret_map[s] -= 1
                bulls.add(i)
        
        cow_count = 0
        for i, g in enumerate(guess):
            if i in bulls:
                continue
            if secret_map.get(g, 0) > 0:
                cow_count += 1
                secret_map[g] -= 1

        return f"{len(bulls)}A{cow_count}B"

Note, len(secret) = len(guess). Say for a given character c, secret[i] = c = guess[i] at k indices. Then, for c, there must be k bulls. So, while processing indices from left to right, at any time if we find secret[i] = c = guess[i] yet secret_map[c] = 0, we know c has been counted as a cow. So, we can correct by reducing cow count. In that way, we can count bulls and cows in one pass.

class Solution:
    def getHint(self, secret: str, guess: str) -> str:
        secret_map = {}
        for c in secret:
            secret_map[c] = secret_map.get(c, 0) + 1

        bull_count, cow_count = 0, 0
        for s, g in zip(secret, guess):
            if g not in secret_map:
                continue

            if s == g: # bull
                bull_count += 1
                if secret_map[s] > 0:
                    secret_map[s] -= 1
                else:
                    cow_count -= 1
            else: # cow
                if secret_map[g] > 0:
                    cow_count += 1
                    secret_map[g] -= 1

        return f"{bull_count}A{cow_count}B"

tanvirdotzaman

,

Leave a comment