題目來源：https://leetcode-cn.com/problems/find-the-difference/submissions/

給定兩個字符串 s 和 t，它們只包含小寫字母。
字符串 t 由字符串 s 隨機重排，然后在隨機位置添加一個字母。
請找出在 t 中被添加的字母。

示例:

輸入：
s = "abcd"
t = "abcde"

輸出：

e

思路：
一個直接的想法就是用counter做字符計數(shù)，t中某個字符不存在與s或者某個字符出現(xiàn)的次數(shù)與s中該字符出現(xiàn)的次數(shù)不一致，則返回該字符。時間復雜度是O(n).

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        from collections import Counter
        
        if len(s) == 0:
            return t
        
        s_counter = Counter(s)
        t_counter = Counter(t)
        
        for key in t_counter:
            if key not in s_counter:
                return key
            elif t_counter[key] != s_counter[key]:
                return key

看題解發(fā)現(xiàn)還有一個比較tricky的解法，利用異或運算的性質(zhì)，一個值連續(xù)對另一個值做兩次異或，會返回它本身，異或運算是可交換的。其實很好理解兩個相同的數(shù)做異或運算結(jié)果為0，而一個數(shù)與0做異或結(jié)果就是它本身。可以利用這個性質(zhì)去消除字符串中的“對子“。

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        new_s = s + t 
        res = 0 
        for i in new_s: 
            res ^= ord(i)
        
        return chr(res)