Find the Difference

• LeetCode: Find the Difference

• Problem:

Given two strings s and t which consist of only lowercase letters.

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

Find the letter that was added in t.

• Examples:

Input:
s = "abcd"
t = "abcde"

Output:
e

Explanation:
'e' is the letter that was added.

• Analysis:

According to the problem description, String t is a random shuffled string from s and add one more letter.

Solution - HashMap.

    1. Use HashMap to count the number of all characters in string t.

    2. Compared to string s.

    3. Get the added letter.

Solution - XOR logic

    XOR Truth Table:
                 -----------------
                 | x | y | x ^ y |
                 ----------------- 
                 | 0 | 0 |   0   |
                 -----------------
                 | 0 | 1 |   1   |
                 -----------------
                 | 1 | 0 |   1   |
                 -----------------
                 | 1 | 1 |   0   |
                 -----------------

As a result, the duplicate character will be 0 via xor operator. 

Only the single character will be left.

1. Solution - HashMap

2. Code - Java:

class Solution {
    public char findTheDifference(String s, String t) {
        Map<Character, Integer> counts = new HashMap<Character, Integer>();
        int lenS = s.length();
        int lenT = t.length();
        for (int i = 0; i < lenT; i++) {
            char ch = t.charAt(i);
            int count = counts.getOrDefault(ch, 0) + 1;
            counts.put(ch, count);
        }
        for (int i = 0; i < lenS; i++) {
            char ch = s.charAt(i);
            int count = counts.getOrDefault(ch, 0) - 1;
            if (count == 0) {
                counts.remove(ch);
            } else {
                counts.put(ch, count);
            }
        }
        char result = ' ';
        for (Character ch : counts.keySet()) {
            result = ch;
        }
        return result;
    }
}

• Code - C++:

class Solution {
public:
    char findTheDifference(string s, string t) {
        map<char, int> counts;
        int lenS = s.size();
        int lenT = t.size();
        for (int i = 0; i < lenT; i++) {
            char ch = t[i];
            int count = 1;
            if (counts.find(ch) != counts.end()) {
                count = counts[ch] + 1;
            }
            counts[ch] = count;
        }
        for (int i = 0; i < lenS; i++) {
            char ch = s[i];
            counts[ch] = counts[ch] - 1;
            if (counts[ch] == 0) {
                counts.erase(ch);
            }
        }
        return counts.begin()->first;
    }
};

• Code - Python:

class Solution(object):
    def findTheDifference(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        counts = {}
        for ch in t:
            count = 1
            if ch in counts.keys():
                count = counts[ch] + 1
            counts[ch] = count
        for ch in s:
            counts[ch] = counts[ch] - 1
            if counts[ch] == 0:
                del counts[ch]
        result = ' '
        for ch in counts.keys():
            result = ch
        return result

• Time Complexity: O(N), N is the length of string t

• Space Complexity: O(N), N is the length of string t

2. Solution - XOR

• Code - Java:

class Solution {
    public char findTheDifference(String s, String t) {
        int lenS = s.length();
        int lenT = t.length();
        int val = 0;
        for (int i = 0; i < lenS; i++) {
            val ^= s.charAt(i) ^ t.charAt(i);
        }
        val ^= t.charAt(lenT - 1);
        return (char)val;
    }
}

• Code - C++:

class Solution {
public:
    char findTheDifference(string s, string t) {
        int lenS = s.size();
        int lenT = t.size();
        int result = 0;
        for (int i = 0; i < lenS; i++) {
            result ^= s[i] ^ t[i];
        }
        result ^= t[lenT - 1];
        return (char)result;
    }
};

• Code - Python:

class Solution(object):
    def findTheDifference(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        result = 0
        for ch in s:
            result ^= ord(ch)
        for ch in t:
            result ^= ord(ch)
        return str(chr(result))

• Code - C:

char findTheDifference(char* s, char* t) {
    int val = 0;
    for (; *s != '\0'; s++) {
        val ^= *s;
    }
    for (; *t != '\0'; t++) {
        val ^= *t;
    }
    return (char)val;
}

• Time Complexity: O(N), N is the length of string s

• Space Complexity: O(1)