leetcode中如何解决找不同问题

题目链接

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 = 0

• XOR运算满足交换律和结合律：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);
        }
    }
};

画解