299. Bulls and Cows

time: O(n), n is min(secret'len, 10)

space:O(1)

class Solution {
    public String getHint(String secret, String guess) {
        int bulls = 0;
        int cows = 0;
        int[] secretCount = new int[10];
        int[] guessCount = new int[10];
        for (int i = 0; i < secret.length(); i++) {
            if (secret.charAt(i) == guess.charAt(i)) {
                bulls++;
            } else {
                secretCount[secret.charAt(i) - '0']++; // record number count
                guessCount[guess.charAt(i) - '0']++;
            }
        }
        for (int i = 0; i < 10; i++) {
            cows += Math.min(secretCount[i], guessCount[i]);
        }
        return bulls + "A" + cows + "B";
    }
}

/*
bulls correct position. x is the number of bulls
cows right number in secret, but in wrong position , can rearrange to be bulls, y is the number of cows

secret(ans), guess, return hint, xAyB


compare two String, if match bulls++
else
 record in counting array, countS[i]++, countG[i]++
 final 
 for (entire countS[]) {
    cows += Math.min(countS[i], countG[i])
 }
 
 
 ex: 
 1123
  b
 0111
 
 bulls = 1
 others not matches, but has common 1'num in both counter  
 
 time: O(n), n is min(secret'len, 10)
 space: O(1)
*/

以這例子來看

1A => 因為 index 1的地方是一樣的

B => guess 的 11 的確在 secret 有, 但不同位置

所以就算 secret 有三個 1 (排除了A的部分), 也只會對到 2個 B

所以這也就是為什麼取 cows += Math.min(countS[i], countG[i]) 就好(也就是交集)

所以也就是為什麼 in else case, 不 match 時, 紀錄每個數字的 count 就可以做 B 了(這些 count 一定是位置不對的 count, 只是還不知道交集有多少個

Last updated

Was this helpful?