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?