# LeetCode Notes: Find the Difference

## Question

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`.

Example 1:

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

Output: "e"

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

Example 2:

Input: s = "", t = "y"

Output: "y"

Constraints:

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

## Solution One

Analysis:

Traverse each letter of the string `t` to determine whether the letter exists in the string `s`, if it exists, delete the letter in `s`, otherwise this letter is the added letter in `t`.

Code:

``````/**
* @param {string} s
* @param {string} t
* @return {character}
*/
var findTheDifference = function (s, t) {
for (const c of t) {
if (s.indexOf(c) !== -1) {
s = s.replace(c, "");
} else {
return c;
}
}
};
``````

## Solution Two

Analysis:

Add up the Unicode encodings of all the letters of the strings `s` and `t` respectively, then subtract the sum of the coded digits of `s` from the sum of the coded digits of `t`, the result is the Unicode encoding of the added letters in `t`.

Code:

``````/**
* @param {string} s
* @param {string} t
* @return {character}
*/
var findTheDifference = function (s, t) {
let as = 0,
at = 0;
for (const cs of s) {
as += cs.charCodeAt();
}
for (const ct of t) {
at += ct.charCodeAt();
}
return String.fromCharCode(at - as);
};
``````

## Solution Three

Analysis:

1. Traverse `s` and count the number of occurrences of each letter of `s`
2. Traverse `t`, deduct the same letters appearing in `t` from the statistical results, once you find that `t` has more letters than `s`, find the letters added in `t`

Code:

``````/**
* @param {string}s
* @param {string} t
* @return {character}
*/
var findTheDifference = function (s, t) {
// Construct an array of length 26 filled with all 0s
const charCount = new Array(26).fill(0);

// Get the char code of the letter a
const aCode = "a".charCodeAt();

// Count the number of occurrences of each letter in s
// For example "acce" statistic result is charCount = [1, 0, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
for (const cs of s) {
charCount[cs.charCodeAt() - aCode]++;
}

// Subtract the letters in t from the above statistics
for (const ct of t) {
charCount[ct.charCodeAt() - aCode]--;

// Once it is found that the number of letters in t is exceeded, find the added letter in t
if (charCount[ct.charCodeAt() - aCode] < 0) {
return ct;
}
}
};
``````

For problems of the same type of solution, please refer to

LeetCode Notes: Ransom Note

## Solution Four

Analysis:

Use the bitwise XOR feature to solve

1. The commutative law is satisfied: `a ^ b ^ c <=> a ^ c ^ b`
2. The XOR of any number and 0 is any number: `0 ^ n => n`
3. The XOR of the same number is 0: `n ^ n => 0`

We take the bitwise XOR of the Unicode encodings of all the letters of the characters `s` and `t`, and the final result is the Unicode encoding of the added letters in `t`.

For example, s = "abcd", t = "abcde",

0 ^ a ^ b ^ c ^ d ^ a ^ b ^ c ^ d ^ e

Equivalent to

a ^ a ^ b ^ b ^ c ^ c ^ d ^ d ^ e

Equivalent to

0 ^ 0 ^ 0 ^ 0 ^ e

Equivalent to

e

Code:

``````/**
* @param {string} s
* @param {string} t
* @return {character}
*/
var findTheDifference = function (s, t) {
let ret = 0;
for (const ch of s) {
ret ^= ch.charCodeAt();
}
for (const ch of t) {
ret ^= ch.charCodeAt();
}
return String.fromCharCode(ret);
};
``````

For problems of the same type of solution, please refer to

LeetCode Notes: Single Number