画解算法：389. 找不同

题目链接 https://leetcode-cn.com/problems/find-the-difference/题目描述 给定两个字符串 s 和 t，它们只包含小写字母。字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。请找出在 t 中被添加的字母。示例:输入：
s = "abcd"
t = "abcde"

输出：
e

解释：
'e' 是那个被添加的字母。
解题方案 思路标签：哈希表本题最容易想到的就是使用哈希表进行运算，遍历第一个字符串标记出现的字符数量，再遍历第二个减去出现的数量，直到遇到为0或者原哈希表就不存在的情况标签：异或运算除了上述方法外，会有一个更tricky的解法，就是使用字符（注意不是字符串）异或运算，尽管并没有降低时间复杂度，但也是一种开阔思路的解题方式使用异或运算可以解题主要因为异或运算有以下几个特点：一个数和0做XOR运算等于本身：a⊕0 = a一个数和其本身做XOR运算等于0：a⊕a = 0XOR运算满足交换律和结合律：a⊕b⊕a = (a⊕a)⊕b = 0⊕b = b故而在以上的基础条件上，将所有数字按照顺序做抑或运算，最后剩下的结果即为唯一的数字时间复杂度：O(m+n)，m为字符串s的长度，n为字符串t的长度代码Java版本class Solution {
    public char findTheDifference(String s, String t) {
        char ans = t.charAt(t.length()-1);
        for(int i = 0; i < s.length(); i++) {
            ans ^= s.charAt(i);
            ans ^= t.charAt(i);
        }
        return ans;
    }
}
JavaScript版本JavaScript由于没有字符位运算所以无法使用异或运算解法。故而使用了第一种哈希表的解法/**
 * @param {string} s
 * @param {string} t
 * @return {character}
 */
var findTheDifference = function(s, t) {
    const map = new Map();
    for(let i = 0; i < s.length; i++) {
        const val = map.get(s[i]);
        map.set(s[i], val === undefined ? 1 : val + 1);
    }
    for(let i = 0; i < t.length; i++) {
        const val = map.get(t[i]);
        if(val === 0 || val === undefined) {
            return t[i];
        } else {
            map.set(t[i], val - 1);
        }
    }
};
画解后台回复「算法」，加入天天算法群觉得算法直击灵魂，欢迎点击在看和转发