[c++] 3ms with "hash table"

  • 0

    Note: this solution is slightly improved from @moumoutsay's [4ms]sln, https://discuss.leetcode.com/topic/28445/c-4ms-straight-forward-solution-two-pass-o-n-time

    class Solution {
    string getHint(string secret, string guess)
    An intuitive solution is to use hash table, but
    take a close look, the input string values are
    limited to char '0'~'9'. Thus, we can use a numberic
    array to mimic hash table with less memory and faster speed
    int aCnt = 0, bCnt = 0; // count bulls (a), cows (b)
    int sVec[10] = {0}, gVec[10] = {0};
    if(secret.size()!=guess.size() || secret.empty()) return "0A0B";
    // count Bulls
    for (int i = 0; i<secret.size();i++)
    if(secret[i]==guess[i]) ++aCnt;
    else {++sVec[secret[i]-'0']; ++gVec[guess[i]-'0']; }

        // count cows
        for(int i = 0;i<10;i++)
            bCnt += min(sVec[i],gVec[i]);
        return to_string(aCnt)+'A'+to_string(bCnt)+'B';


Log in to reply

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