O(n) time and O(n) space, simple C++ implementation


  • 0
    T
    class Solution {
    public:
        string getHint(string secret, string guess) {
            int n = secret.length();
            if(n==0)
                return "0A0B";
            int count=0;
            int countleft[10]= {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
            int countright[10]= {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
            char *left = (char*) malloc(n);
            char *right = (char*) malloc(n);
            strcpy(left, secret.c_str());
            strcpy(right, guess.c_str());
            for(int i=0; i<n; i++)
            {
                if(left[i] == right[i])
                    count++;
                int num;
                num = (int) (left[i] - '0');
                countleft[num] ++;
                num = (int) (right[i] - '0');
                countright[num] ++;
            }
            
            int count2 = 0;
            for(int j=0; j<10; j++)
                count2 = count2 + min(countleft[j], countright[j]);
            string s = to_string(count);
            s = s + "A";
            s = s + to_string(count2 - count);
            s = s + "B";
            
            free(right);
            free(left);
            return s;
        }
    };

Log in to reply
 

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