389. 找不同

解题过程

INFO

题目链接给定两个字符串 s 和 t ，它们只包含小写字母。字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。请找出在 t 中被添加的字母

javascript

/**
 * @link https://leetcode.cn/problems/find-the-difference/
 * @title 389. 找不同
 * @description 给定两个字符串 s 和 t ，它们只包含小写字母。
 * 字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。
 * 请找出在 t 中被添加的字母
 * @param {string} s
 * @param {string} t
 * @return {character}
 */
// 解法一
// 思路：统计t和s字符串每个字母出现的次数，对比字母数量即可知道
// 缺点：操作次数比较多，要循环遍历3次
var findTheDifference = function (s, t) {
  const tMap = new Map()
  const sMap = new Map()

  // for (let i = 0; i < t.length; i++) {
  //   if (tMap.has(t[i])) {
  //     tMap.set(t[i], tMap.get(t[i]) + 1)
  //   } else {
  //     tMap.set(t[i], 1)
  //   }
  // }
  // 代码优化👆🏻
  for (const key of t) {
    tMap.set(key, (tMap.get(key) || 0) + 1)
  }

  // for (let i = 0; i < s.length; i++) {
  //   if (sMap.has(s[i])) {
  //     sMap.set(s[i], sMap.get(s[i]) + 1)
  //   } else {
  //     sMap.set(s[i], 1)
  //   }
  // }
  // 代码优化👆🏻
  for (const key of s) {
    sMap.set(key, (sMap.get(key) || 0) + 1)
  }

  for (const [key, value] of tMap) {
    if (value !== sMap.get(key)) {
      return key
    }
  }
}

// 解法二
// 思路：针对解法一优化，最多遍历两次即可
var findTheDifference = function (s, t) {
  const sMap = new Map()

  for (const key of s) {
    sMap.set(key, (sMap.get(key) || 0) + 1)
  }

  for (let i = 0; i < t.length; i++) {
    if (sMap.has(t[i]) && sMap.get(t[i]) !== 0) {
      sMap.set(t[i], sMap.get(t[i]) - 1)
    } else {
      return t[i]
    }
  }
}

// 解法二
// 思路：使用正则表达式做字符匹配，匹配结果是否相等来判断当前字母是否新增的即可
// 优点：相对上面执行次数更少且更好
var findTheDifference = function (s, t) {
  for (let i = 0; i < t.length; i++) {
    const reg = new RegExp(`${t[i]}`, 'g')
    if (s.match(reg)?.length !== t.match(reg)?.length) {
      return t[i]
    }
  }
}

// const result = findTheDifference('abcd', 'abcde') // e
// const result = findTheDifference('', 'y') // e
const result = findTheDifference('a', 'aa') // a
console.log(result)

解题感受

使用了三种解法，第一种解法相对比较笨方法，第二种针对第一种解法进行了优化至少减少了一次循环，第三种方法就更简单了——使用了正则表达式，循环遍历一次即可。看了官方的题解使用求和用 Ascii 码解和位运算很新颖的解法，下次遇到类似的问题可以尝试这样解。

389. 找不同 ​

解题过程 ​

解题感受 ​

优质题解 ​

389. 找不同

解题过程

解题感受

优质题解