leetcode-hashmap

299. Bulls and Cows.py

class Solution:
    """
    PQ:
        -Can I assume len(secret) == len(guess)? Yes
        -Contain digit only in the given string
    Thought Process:
        Two-passes:
            step1: count bulls is easy, just traverse two strings together, O(n). In the mean time, we keep track of frequenc of un-matched character in secrect, in order to use later.
            step2: count cows. just traverse guess, O(n). If currend index of secret != current guess and secret_cnt[g] > 0:
            cow+=1
            secret_cnt[g]-=1
    example:
        secret = "1949"
        guess = "4422"
        only the first 4 counted as 4-cow
    Ref:
        https://www.youtube.com/watch?v=VixxJlwSlZE&ab_channel=codingya
    """
    def getHint(self, secret: str, guess: str) -> str:
        """
        T: O(n), we pass over the strings two times. 
        S: O(1) to keep hashmap h which contains at most 10 elements.
        """
        # step1: to count bulls and use hashmap to store frequency of un-matched character in secrect
        secret_cnt = collections.defaultdict(int)
        bulls = 0
        for s, g in zip(secret, guess):
            if s == g:
                bulls+=1
            else:
                secret_cnt[s]+=1
        # step1: to count cows by iterating guess
        cows = 0
        for i, g in enumerate(guess):
            if secret[i] != g and secret_cnt[g]:
                cows+=1
                secret_cnt[g]-=1
        
        return "{}A{}B".format(bulls, cows)