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 只包含小写字母#

题解

1. 分别遍历 s 和 t，并使用哈希表分别记录里面字符出现的次数，再一次遍历代表 t 的哈希表，如果 t 的哈希表包含 s 哈希表没有的元素，或者对应的数字不等，那么说明这个元素为多出来的。

TIP

执行用时：92 ms, 在所有 JavaScript 提交中击败了 63.65% 的用户
内存消耗：39.6 MB, 在所有 JavaScript 提交中击败了 37.13% 的用户

/**
 * @param {string} s
 * @param {string} t
 * @return {character}
 */
var findTheDifference = function(s, t) {
    if(s == '') return t
    
    let hash1 = {}
    let hash2 = {}
    for(let i=0;i<s.length;i++) {
        if(hash1[s[i]] == undefined) {
            hash1[s[i]] = 1
        } else {
            hash1[s[i]] += 1
        }
    }
    
    for(let i=0;i<t.length;i++) {
        if(hash2[t[i]] == undefined) {
            hash2[t[i]] = 1
        } else {
            hash2[t[i]] += 1
        }
    }

    for(let key in hash2) {
        if(hash1[key] == undefined) {
            return key
        } else if (hash2[key] !== hash1[key]) {
            return key
        }
    }
};

• 时间复杂度： `O(n)`，分别使用两个 for循环，一个 for in 循环。使用 O(1) 的复杂度来判断元素是否存在`
• 空间复杂度： `O(n)`，使用两个对象结构来储存值
• 最好情况： 尽早的出现多余的值
• 最坏情况： 在字符串的末尾发现重复的值

2. 思路是分别遍历 s 和 t，并把对应字符的 unicode 字符编码相加，最后做减法求出对应的字符。

TIP

执行用时：92 ms, 在所有 JavaScript 提交中击败了 63.65% 的用户
内存消耗：38.4 MB, 在所有 JavaScript 提交中击败了 77.72% 的用户

/**
 * @param {string} s
 * @param {string} t
 * @return {character}
 */
var findTheDifference = function(s, t) {
    if(s == '') return t
    
    let code1 = 0
    let code2 = 0
    
    for(let i=0;i<s.length;i++) {
        code1 += s.charCodeAt(i)
    }
    for(let i=0;i<t.length;i++) {
        code2 += t.charCodeAt(i)
    }

    return String.fromCharCode(code2 - code1)
};

• 时间复杂度： `O(n)`，分别使用两个 for循环
• 空间复杂度： `O(1)`，使用两个变量来储存值
• 最好情况：
• 最坏情况：