Coming off a weekend away from the computer and greeted with a long Monday at work. Didn't have time to grind one out this morning so figured I'd start with something easy this evening.
Beats 100.00% of users with C++ on time.
Beats 17.51% of users with C++ on space.
Approach
The objective is to find the added item in t that is not in s.
This sounds like a classic unordered_map problem. I believe there is also a trick to XOR the chars together which would reveal the missing item but haven't explored this yet so take that with a grain of salt.
My approach is simple.
Using an unordered_map, I iterate over s. On each character, I subtract 1 from the value for that char in the map.
Conversely, on each character in t, I add 1 to the value for that char in the map.
In the end, I am left with a map of elements where one element should equal 1, indicating the item that was added to t and that is not in s.
The last item to do is to loop over the keys in the unordered_map and if the it->second == 1, return the key (it->first).
Complexity
Time Complexity: O(n)
Space Complexity: O(n)
Code
class Solution {
public:
char findTheDifference(string s, string t) {
unordered_map<char, int> m;
for(char c : s){
m[c]--;
}
for(char c : t){
m[c]++;
}
for(auto it = begin(m); it != end(m); it++){
if(it->second == 1) return it->first;
}
return NULL;
}
};