Javascript Solution Find the Difference
In this article we will solve leetcode problem `Find the Difference' using Bit Manipulation.
Problem Overview
There are two string s and t.
String t is generated by random shuffling string s and then add one more letter at a random position.
We have to return added letter.
For exact problem visit Leetcode Link;
Sample Input Output
Input: s = "abcd", t = "abcde"
Output: "e"
Explanation: 'e' is the letter that was added.Javascript Solution
Essentially we will be taking advantage of the Bitwise XOR ^ operator. For every NUMBER X, we have
X^X=0 and X^0=X So the plan is:
- Iterate over the shortest array
s - Keep accumulating (XOR ^ing) the elements of both
sandt, after we have converted them to Numbers with CharCodeAt() so the XOR can work. Elements that appear both intandswill give us zero (X^X=0), yet that zero will not affect the total sum (X^0=X) - Return the converted back to character final sum, which is essentially the (desired) character not present in s
Original Solution Link GeorgeChryso;
const findTheDifference = function(s, t) {
let sum=0 // initialize the accumulator
// t.length > s.length because there will always be 1 extra letter on t (the one we want to return)
for (let i = 0; i < s.length; i++) {
sum^= // accumulate with XOR
t[i].charCodeAt()^ // the converted to Number t[i]
s[i].charCodeAt() // along with a converted to Number s[i],
}
sum^=t[i].charCodeAt() // add the remaining letter of t
return String.fromCharCode(sum) // return the converted to Character total
};
Quick example:
s='abcd' , t='dcbqa'Same Algorithm Implementation Using ES6
/**
* @param {number} x
* @return {number}
*/
var findTheDifference = function (s, t) {
return String.fromCharCode(
[...s, ...t].reduce((acc, c) => {
return acc ^ c.charCodeAt(0)
}, 0)
)
}