Leetcode 389 - Find the diff

Note:

  • Use hash table is straightforward.
  • Use XOR operation. Convert char into ASCII code, then XOR them all together. The extra char will be left because the number of every char excep the extra is even, which make charCode ^ charCode === 0. And 0 ^ extraCharCode === res

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
2
3
Input: s = "abcd", t = "abcde"
Output: "e"
Explanation: 'e' is the letter that was added.

Code:

HashTable with O(n) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* @param {string} s
* @param {string} t
* @return {character}
*/
var findTheDifference = function(s, t) {
let sMap = new Map();
for (const char of s) {
if (!sMap.has(char)) {
sMap.set(char, 1);
} else {
sMap.set(char, sMap.get(char) + 1);
}
}
for (const char of t) {
if (!sMap.has(char) || sMap.get(char) === 0) return char;
sMap.set(char, sMap.get(char) - 1);
}
};

Bitwise with O(1) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* @param {string} s
* @param {string} t
* @return {character}
*/
var findTheDifference = function(s, t) {
let res = 0;
for (const char of s) {
res ^= char.charCodeAt();
}
for (const char of t) {
res ^= char.charCodeAt(0);
}
return String.fromCharCode(res);
};