Java/Python O(n) solutions


  • 1

    Calculate bulls is easy. Just sum all the characters that are equal. To calculate cows, first, we use Counter to get digit counts for both secret and guess. For each digit, its contribution is the min of its occurrence in the two strings and Counter provides the "&" operator to do the min thing. cows is then sum of all these min values subtract bulls.

    Python solution with Counter

    from collections import Counter
    def getHint(self, secret, guess):
        bulls = sum(g == s for g, s in zip(secret, guess))
        cows = sum((Counter(secret) & Counter(guess)).values()) - bulls
        return "{0}A{1}B".format(bulls, cows)
    
    # Runtime: 76 ms
    

    Java one pass solution

    public class Solution {
        public String getHint(String secret, String guess) {
            int bulls = 0, cows = 0;
            int[] s = new int[10];
            for (int i = 0; i < secret.length(); ++i) {
                int sc = Character.getNumericValue(secret.charAt(i));
                int gc = Character.getNumericValue(guess.charAt(i));
                if (sc == gc) ++bulls;
                else {
                    if (s[sc] < 0) ++cows;
                    if (s[gc] > 0) ++cows;
                    ++s[sc];
                    --s[gc];
                }
            }
            return String.format("%dA%dB", bulls, cows);
        }
    }
    // Runtime: 18 ms

  • 0
    H

    Nice ans, thanks for sharing


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.