Bulls and Cows

You are playing the following Bulls and Cows game with your friend: You write down a number and ask your friend to guess what the number is. Each time your friend makes a guess, you provide a hint that indicates how many digits in said guess match your secret number exactly in both digit and position (called “bulls”) and how many digits match the secret number but locate in the wrong position (called “cows”). Your friend will use successive guesses and hints to eventually derive the secret number.

Write a function to return a hint according to the secret number and friend’s guess, use A to indicate the bulls and B to indicate the cows.

Please note that both secret number and friend’s guess may contain duplicate digits.

Example 1:

Input: secret = “1807”, guess = “7810”

Output: “1A3B”

Explanation: 1 bull and 3 cows. The bull is 8, the cows are 0, 1 and 7.
Example 2:

Input: secret = “1123”, guess = “0111”

Output: “1A1B”

Explanation: The 1st 1 in friend’s guess is a bull, the 2nd or 3rd 1 is a cow.
Note: You may assume that the secret number and your friend’s guess only contain digits, and their lengths are always equal.

这题其实要解决不难，但是O(N)的时间复杂度和O(1)的空间复杂度的算法可能不容易一下子就想到，下面分析一下这种算法的思路：

创建一个大小为10的数组用于存储0-9每个值出现的次数。

顺序扫描secret和guess下每个同位置字符，假如相等，则把bull的计数加1，假如不等，则查看数组secret值对应位置的计数，假设大于0，说明guess曾经出现过，那么把cow计数加1，然后无论cow有没有加1，都把计数减去1；然后再看guess值在数组中对应出现的次数，假如小于0，说明secret曾经出现过，那么也把cow值加1，然后无论cow有没有加1，都把计数加上1。这样就能一次循环解决问题，下面贴解法：

string getHint(string secret, string guess) {
    int tms[10] = {0};
    int bull = 0, cow = 0;
    for (int i = 0; i < secret.size(); i++) {
        if (secret[i] == guess[i]) {
            ++bull;
        } else {
            if (tms[secret[i] - '0'] > 0) {
                ++cow;
            }
            --tms[secret[i] - '0'];
            if (tms[guess[i] - '0'] < 0) {
                ++cow;
            }
            ++tms[guess[i] - '0'];
        }
    }
    return std::to_string(bull) + "A" + std::to_string(cow) + "B"; 
}