C++, one pass, O(N) time, O(1) space


  • 11
    C
    class Solution {
    public:
        string getHint(string secret, string guess) {
            unordered_map<char, int> s_map;
            unordered_map<char, int> g_map;
            int n = secret.size();
            int A = 0, B = 0;
            for (int i = 0; i < n; i++)
            {
                char s = secret[i], g = guess[i];
                if (s == g)
                    A++;
                else
                {
                    (s_map[g] > 0) ? s_map[g]--, B++ : g_map[g]++;
                    (g_map[s] > 0) ? g_map[s]--, B++ : s_map[s]++; 
                }
            }
            return to_string(A) + "A" + to_string(B) + "B";;
        }         
    };

  • 0

    Why is this O(n) space? I suppose your n is the length of the string. You only have 2 hash maps.
    Your space is O(k) and k is number of keys which is at most 10.


  • 0
    C

    I just extend this solution to solve all possible characters, which needs O(N) space. In this problem, only 10 possible characters. I agree with you only O(1) space required in this problem.


  • 0

    I see your point.


Log in to reply
 

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