Two C++ solutions, bit manipulation, hash table


  • 0
    A

    Method 1: bit manipulation
    O(n) time, O(1) space

    class Solution {
    public:
        char findTheDifference(string s, string t) {
            char ans = 0;
            for (char c : s)
                ans ^= c;
            for (char c : t)
                ans ^= c;
            return ans;
        }
    };
    

    Method 2: hash table (using array)
    O(n) time, O(1) space (array of O(26))

    class Solution {
    public:
        char findTheDifference(string s, string t) {
            vector<int> f(26, 0);
            for (char c : t)
                ++f[c - 'a'];
            for (char c : s)
                --f[c - 'a'];
            for (int i = 0; i < 26; ++i) {
                if (f[i])
                    return i + 'a';
            }
            return 0;
        }
    };
    

Log in to reply
 

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