# 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:**

- Traverse
`s`

and count the number of occurrences of each letter of`s`

- 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

## Solution Four

**Analysis:**

Use the bitwise XOR feature to solve

- The commutative law is satisfied:
`a ^ b ^ c <=> a ^ c ^ b`

- The XOR of any number and 0 is any number:
`0 ^ n => n`

- 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

## Comments