找不同-389

[sl1673495]

给定两个字符串 s 和 t，它们只包含小写字母。

字符串  t  由字符串  s  随机重排，然后在随机位置添加一个字母。

请找出在 t 中被添加的字母。

示例:

输入：
s = "abcd"
t = "abcde"

输出：
e

解释：
'e' 是那个被添加的字母。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-the-difference
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

查找 map

分别为 s 和 t 记录一个字符出现数量的 map，然后遍历长度更长的那个字符串的 map，如果发现某个 key 在另一个 map 中没有出现，那么多出来的就是那个 key 的字符。

/**
 * @param {string} s
 * @param {string} t
 * @return {character}
 */
let findTheDifference = function (s, t) {
  let mapS = createCharsMap(s)
  let mapT = createCharsMap(t)

  let targetMap = s.length > t.length ? mapS : mapT
  let otherMap = targetMap === mapS ? mapT : mapS
  let keys = Object.keys(targetMap)
  for (let key of keys) {
    if (targetMap[key] !== otherMap[key]) {
      return key
    }
  }
}

function createCharsMap(s) {
  let map = {}
  for (let i = 0; i < s.length; i++) {
    let char = s[i]
    if (!map[char]) {
      map[char] = 1
    } else {
      map[char]++
    }
  }
  return map
}

位运算

利用 ^ 异或运算，不断的异或字符的 charCode 值，相同的值都会消除为 0，最后剩下的就是多出来的字符的 charCode 值。

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

[SpiritSamllFire]

用ES6 Map替换了一下，更方便看。^ ^ LC能跑进80ms

function findTheDifference(s, t) {
    const mapS = createCountMap(s);
    const mapT = createCountMap(t);

    const longerMap = mapS.size > mapT.size ? mapS : mapT;
    const shorterMap = longerMap === mapS ? mapT : mapS;

    for (let key of longerMap.keys()) {
        if(shorterMap.get(key) !== longerMap.get(key)) {
            return key;
        }
    }

};

function createCountMap(str) {
    const res = new Map();
    for (const char of str) {
        if(!res.get(char)){
            res.set(char, 1);
        } else {
            res.set(char, res.get(char)+1);
        }
    }

    return res;
} 

[vortesnail]

似乎可以简化点写法呢：

var findTheDifference = function (s, t) {
  const sMap = new Map();
  for (const c of s) {
    sMap.set(c, (sMap.get(c) || 0) + 1);
  }
  const tMap = new Map();
  for (const c of t) {
    tMap.set(c, (tMap.get(c) || 0) + 1);
  }
  // 遍历 tMap，根据两者数量是否一致确定
  for (const [key, value] of tMap) {
    if (sMap.get(key) !== value) {
      return key;
    }
  }
};

[vortesnail]

利用 ascii 码的计算差值再转换也比上面会更快些：

var findTheDifference = function (s, t) {
  let sum = 0;
  for (const c of t) {
    sum += c.charCodeAt();
  }
  for (const c of s) {
    sum -= c.charCodeAt();
  }
  return String.fromCharCode(sum);
};

[btqf]

直接用一个哈希表即可：

var findTheDifference = function(s, t) {
    const len = s.length;
    if (!len) return t;
    const map = new Map();
    for (let item of s) {
        map.set(item, (map.get(item) || 0) + 1);
    }
    for (let item of t) {
        if (map.has(item)) {
            map.set(item, map.get(item) - 1);
        } else {
            return item
        }
    }
    for (let key of map.keys()) {
        if (map.get(key) === -1) return key
    }
};

[keer-tea]

function fn(s: string, t: string) {
  const sArr = s.split('')
  const tArr = t.split('')
  for(let i = 0; i < sArr.length; i ++) {
    const char = sArr[i]
    const index = tArr.findIndex(item => item === char)
    tArr.splice(index, 1)
  }
  return tArr[0]
}

[btqf]

邮件已收到，祝一切安好~