👨‍💻

389. Find the Difference

https://leetcode.com/problems/find-the-difference/March 4, 2021

leetcode algorithm

On this page

Complete Data: 2020-09-24
Description
Example
Solution
Complexity Analysis

Complete Data: 2020-09-24

Description

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.

Solution

/**
 * @param {string} s
 * @param {string} t
 * @return {character}
 */
var findTheDifference = function (s, t) {
  "use strict";
  for (let i = 0; i < s.length; i++) {
    t = t.replace(s[i], "");
  }
  return t;
};

Solution 2

/**
 * Solved with bit manipulation (   )
 * @param {string} s
 * @param {string} t
 * @return {character}
 */
var findTheDifference = function (s, t) {
  const n = t.length;
  let c = t.charCodeAt(n - 1);
  for (let i = 0; i < n - 1; i++) {
    c ^= s.charCodeAt(i);
    c ^= t.charCodeAt(i);
  }

  return String.fromCharCode(c);
};

^(XOR) Sets each bit to 1 if only one of two bits is 1

Complexity Analysis

Edit this page