题目链接

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);
       }
   }
};

画解