Find the Difference

Problem

You are given two strings s and t.

String t is generated by random shuffling string s and then add one more letter at a random position.

Return the letter that was added to t.

Constraints

• 0 <= s.length <= 1000
• t.length == s.length + 1
• s and t consist of lowercase English letters.

Solution

The problem Find the Difference can be solved using an XOR operator. Let X(s) be a result of performing XOR operations on all characters in a string s. Then X(t) = t[0] ^ t[1] ^ ... ^ t[t.length() - 1] = s[0] ^ s[1] ^ ... ^ s[s.length() - 1] ^ k = X(s) ^ k where k is the single letter that is added to t. Therefore, k can be found by performing XOR operation on X(s) and X(t) as X(s) ^ X(t) = X(s) ^ (X(s) ^ k) = k.

Implementation

class Solution
{
  public:
    char findTheDifference(string s, string t)
    {
        char ret = 0;
        for (int i = 0; i < s.length(); i++)
            ret ^= t[i] ^ s[i];

        return ret ^ t.back();
    }
};