# Question

Formatted question description: https://leetcode.ca/all/389.html

 389	Find the Difference

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.

Example:

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

Output:
e

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



# Algorithm

Use a hash table to establish a mapping between characters and numbers. If a mapping value is less than 0 when traversing t, then return the character.

You can also use addition and subtraction directly, the same character minus one plus also cancels out, the rest is the character added later.

Also, Bit Manipulation by using the property of XOR, the same bit returns 0, so that the same characters are cancelled out, and the rest is the character added later

# Code

Java

• 
public class Find_the_Difference {

class Solution_xor {
public char findTheDifference(String s, String t) {
char res = 0;
for (char c : s.toCharArray()) res ^= c;
for (char c : t.toCharArray()) res ^= c;
return res;
}
}

class Solution_plusMinus {
public char findTheDifference(String s, String t) {
char res = 0;
for (char c : s.toCharArray()) res -= c;
for (char c : t.toCharArray()) res += c;
return res;

}
}

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

• // OJ: https://leetcode.com/problems/find-the-difference/
// Time: O(N)
// Space: O(1)
class Solution {
public:
char findTheDifference(string s, string t) {
int cnt = {};
for (char c : s) cnt[c - 'a']++;
for (char c : t) {
if (--cnt[c - 'a'] < 0) return c;
}
return 0;
}
};

• class Solution(object):
def findTheDifference(self, s, t):
"""
:type s: str
:type t: str
:rtype: str
"""
sum1 = sum(map(ord, [c for c in s]))
sum2 = sum(map(ord, [c for c in t]))
return chr(sum2 - sum1)