389. 找不同.md

389. 找不同

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

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

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

示例 1：

输入：s = "abcd", t = "abcde"
输出："e"
解释：'e' 是那个被添加的字母。

示例 2：

输入：s = "", t = "y"
输出："y"

示例 3：

输入：s = "a", t = "aa"
输出："a"

示例 4：

输入：s = "ae", t = "aea"
输出："a"

提示：

• 0 <= s.length <= 1000
• t.length == s.length + 1
• s 和 t 只包含小写字母

思路

使用map将t中的char对应的count存起来，然后遍历s一个个减去 ，留下最后多出来的字符

代码

/**
 * @param {string} s
 * @param {string} t
 * @return {character}
 */
var findTheDifference = function(s, t) {
  let obj = {};
  for(let i = 0; i < t.length; i ++) {
    let cur = t[i]
    obj[cur] = (obj[cur] || 0) + 1
  }
  for(let i = 0; i < s.length; i ++) {
    let cur = s[i]
    obj[cur] = obj[cur] - 1
    if (obj[cur] === 0) {
      delete obj[cur]
    }
  }
  for(let key in obj) {
    return key
  }
};

复杂度分析

时间复杂度 $O(N)$

空间复杂度 $O(N)$