Java 3ms Solution with explanation


  • 1
    B

    The difficulty of this problem really just lies in the bookkeeping. The problem asks you to both identify identical digits at the same index while still asking that you keep track of digits that are shared between the two but out of place. Checking to see if a digit is in either suggests a Set. However, that won't work because we may have more than one of the same digit. So keeping a count of some kind seems like the best way to go. My solution is as follows:

       public String getHint(String secret, String guess) {
        int[] secretCounts = new int[10];
        int[] guessCounts = new int[10];
        
        int bulls = 0;
        int cows = 0;
        
        for (int i = 0; i < secret.length(); i++)
        {
            char s = secret.charAt(i);
            char g = guess.charAt(i);
            int sInt = s - '0';
            int gInt = g - '0';
            if (sInt == gInt)
            {
                bulls++;
            }
            else
            {
                secretCounts[sInt]++;
                guessCounts[gInt]++;
            }
        }
        
        for (int i = 0; i < 10; i++)
        {
            cows += Math.min(secretCounts[i], guessCounts[i]);
        }
        return bulls + "A" + cows + "B";
    }
    

    This solution works by creating two arrays. One to keep track of all the counts for the digits in secret and one for all the digits in guess. These will only keep track of the digits that do not line up with one another. If the digits do line up, we are done at that position and we just increment the bulls variable. Essentially we are using the first pass over the strings to find all of the digits that line up and create a record of the ones that don't. We can then do one additional pass over the arrays, taking the min at the same indexes. This works because if secret has, for example, four 1's and guess only has two 1's then only two of those can be cows. So we can safely add all the min of secretCounts[i] and guessCounts[i] to the cows.

    This provides a quick, easy to understand, O(n) solution.


Log in to reply
 

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