25th_Find_the_Difference.md

Find the Difference

https://leetcode.com/problems/find-the-difference/description

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.

Approach 1

Brute force

    char findTheDifference(string s, string t) {
        std::sort(s.begin(), s.end());
        std::sort(t.begin(), t.end());

        for (size_t i = 0; i < s.length(); i++)
        {
            if (s[i] != t[i])
            {
                return t[i];
            }
        }

        return t.back();
    }

Approach 2

Sum

    char findTheDifference(string s, string t) {
        int diff = 0;
        for (size_t i = 0; i < s.length(); i++)
        {
            diff -= s[i];
            diff += t[i];
        }

        diff += t.back(); // t.length = s.length + 1

        return (char)diff;

Approach 3

XOR

    char findTheDifference(string s, string t) {
        char diff = 0;
        for (const char& ch : s + t)
        {
            diff ^= ch;
        }
        return diff;
    }