Description

sl1673495

opened on Jun 29, 2020

Issue body actions

给定两个字符串 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)
}

Activity

1. sl1673495

   added

   查找表

   位运算

   待复习看题解或者做出来很艰难的，需要回顾。看题解或者做出来很艰难的，需要回顾。

   on Jun 29, 2020
2. SpiritSamllFire commented on May 1, 2021

   

   SpiritSamllFire

   on May 1, 2021

   More actions

   用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;
   } 
   
3. vortesnail commented on Jul 31, 2021

   

   vortesnail

   on Jul 31, 2021

   More actions

   似乎可以简化点写法呢：

   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;
       }
     }
   };
4. vortesnail commented on Jul 31, 2021

   

   vortesnail

   on Jul 31, 2021

   More actions

   利用 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);
   };

   Reacted by Bacuuu and keshi
5. btqf commented on Sep 27, 2022

   

   btqf

   on Sep 27, 2022

   More actions

   直接用一个哈希表即可：

   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
       }
   };
   
6. keer-tea commented on Feb 1, 2023

   

   keer-tea

   on Feb 1, 2023

   More actions

   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]
   }
7. btqf commented on Feb 1, 2023

   

   btqf

   on Feb 1, 2023 via email

   More actions

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

Issue actions