LeetCode -- Bulls and Cows

Question:

You are playing the following Bulls and Cows game with your friend: You write a 4-digit secret number and ask your friend to guess it. Each time your friend guesses a number, you give a hint. The hint tells your friend how many digits are in the correct positions (called "bulls") and how many digits are in the wrong positions (called "cows"). Your friend will use those hints to find out the secret number.

For example:

Secret number:  "1807"
Friend's guess: "7810"

Hint: 1 bull and 3 cows. (The bull is 8, the cows are 0, 1 and 7.)

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. In the above example, your function should return "1A3B".

Please note that both secret number and friend's guess may contain duplicate digits, for example:

Secret number:  "1123"
Friend's guess: "0111"

In this case, the 1st 1 in friend's guess is a bull, the 2nd or 3rd 1 is a cow, and your function should return "1A1B".

You may assume that the secret number and your friend's guess only contain digits, and their lengths are always equal.

Analysis:

题目描述：你与你的朋友玩“公牛与母牛”的游戏：你写出4位秘密数字，然后让你的朋友猜出它。每次你的朋友给出一组数字，你都要给出一些hint。这些线索能够告诉你的朋友有多少位数字在正确的位置上（“公牛”），和有多少数字在错误的位置上（“母牛”）。你的朋友将会根据你给出的提示找到正确地数字。

例如：

秘密数字是：“1807”

朋友给出的数字是：“7810”

提示是：1个bull和3个cows.(bull是8， cows分别是7、1、0)

写一个函数能够根据你和朋友的数字给出hint，用A表示bulls，用B表示cows。在上面的例子中，你的函数应该返回“1A3B”。

请注意：在你给出的秘密数字和朋友给出的猜测中可能出现重复数字。例如：

秘密数字：“1123”

朋友给出的数字：“0111”

在这种情况下，第一个1是bull, 第2 or 3个1是cow，你的函数应该返回“1A1B”。

你可以假设你的秘密数字和朋友给出的仅仅包含数字，并且他们的长度是相等的。

思路：该问题是找出朋友给出的数字中数字和位置都正确的和位置错误的。

首先遍历一遍，在遍历的过程中，记录匹配的正确地个数，同时用两个hashMap记录secret和guess字符串中分别出现的数字及个数，然后在错误匹配中加入较小的值即可。

Answer:

import java.util.Map.Entry;
public class Solution {
  public static String getHint(String secret, String guess) {
            int a = 0, b = 0; //分别用来记录A B的数目
            char[] secretCh = secret.toCharArray();
            char[] guessCh = guess.toCharArray();
            HashMap<Character, Integer> map1 = new HashMap<Character, Integer>();
            HashMap<Character, Integer> map2 = new HashMap<Character, Integer>();
            for(int i=0; i<secretCh.length; i++) {
                if(secretCh[i] == guessCh[i]) {
                    a++;
                }
                else {
                    if(map1.containsKey(secretCh[i])) {
                        int key = map1.get(secretCh[i]);
                        map1.put(secretCh[i], ++key);
                    } else {
                        map1.put(secretCh[i], 1);
                    }
                    
                    if(map2.containsKey(guessCh[i])) {
                        int key = map2.get(guessCh[i]);
                        map2.put(guessCh[i], ++key);
                    } else {
                        map2.put(guessCh[i], 1);
                    }
                }
            }
            Iterator it = map1.entrySet().iterator();
            while(it.hasNext()) {
                Entry entry = (Entry) it.next();
                Character key = (Character) entry.getKey();
                Integer value = (Integer) entry.getValue();
                if(map2.containsKey(key)) {
                    b += value < map2.get(key) ? value : map2.get(key);
                }
            }
            
            StringBuffer sb = new StringBuffer();
            sb.append(Integer.toString(a));
            sb.append("A");
            sb.append(Integer.toString(b));
            sb.append("B");
            return sb.toString();
    }
   
}