Skip to content

Latest commit

 

History

History
66 lines (46 loc) · 1.47 KB

Find the Difference.md

File metadata and controls

66 lines (46 loc) · 1.47 KB

Find the Difference

题目:

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.

翻译:

给予两个只包含小写字母的字符串s和t

字符串t是通过随机打乱s,然后在随机的位子增加一个字母。

找到这个增加的字母

例子:

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

Output:
e

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

思路:

其实,方法有很多种,时间复杂度从O(n),到O(nlogn),再到O(n^2)的。

我们可以来分析一下O(n)的情况

首先,介绍两个函数:

  • charCodeAt():将字符转成ASCII码
  • fromCharCode():将ASCII码转成字符
  • 我们可以通过异或的方式,记得之前做过一道题目,在重复两次的数组中找出只有一次的数字,其实,这里也是同样的道理。s和t都是重复的,唯一的就是t中随机多出来的那个字符
  • 但是,这里使用异或时,我们需要将字符转成ASCII码

代码实现:

/**
 * @param {string} s
 * @param {string} t
 * @return {character}
 */
var findTheDifference = function(s, t) {
    let r = '0';
    for(let i = 0; i < s.length; i++){
        r ^= s[i].charCodeAt();
    }
    for(let i = 0; i < t.length; i++){
        r ^= t[i].charCodeAt();
    }
    return String.fromCharCode(r);
};