难度: Easy
给定两个字符串 s 和 t ，它们只包含小写字母。
字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。
请找出在 t 中被添加的字母。
示例 1：
输入：s = "abcd", t = "abcde" 输出："e" 解释：'e' 是那个被添加的字母。
示例 2：
输入：s = "", t = "y" 输出："y"
提示：
0 <= s.length <= 1000t.length == s.length + 1s和t只包含小写字母
Submission
运行时间: 19 ms
内存: 16.1 MB
from collections import Counter
# from collections import defaultdict
class Solution:
def findTheDifference(self, s: str, t: str) -> str:
res = 0
for ch in t+s:
res = res^ord(ch)
return chr(res)
Explain
这个题解的思路是利用位运算中的异或操作来找出额外添加的字母。将字符串 s 和 t 中的每个字符转换为其 ASCII 码，然后对所有字符的 ASCII 码进行异或运算。由于异或运算有以下性质：a^a=0, a^0=a, a^b^b=a，所以将 s 和 t 中所有字符的 ASCII 码异或，最终得到的结果就是额外添加字符的 ASCII 码。最后将这个 ASCII 码转换回字符即可。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def findTheDifference(self, s: str, t: str) -> str:
# 初始化变量 res 用于存储异或结果
res = 0
# 遍历字符串 t 和 s 中的每个字符
for ch in t+s:
# 将当前字符的 ASCII 码与 res 进行异或运算
res = res^ord(ch)
# 将最终的异或结果 res 转换回字符并返回
return chr(res)
Explore
使用异或操作的主要优势在于其空间效率和执行效率。异或操作只需要一个变量来存储结果，从而具有O(1)的空间复杂度，而哈希表或计数方法通常需要额外的空间来存储每个字符的计数，具有O(n)的空间复杂度。此外，异或操作的时间复杂度为O(n)，与哈希表或计数方法相同，但在实际执行中，由于只涉及简单的位运算，其执行速度通常更快。
异或运算具有交换律和结合律，意味着无论操作的顺序如何，结果是相同的。由于异或运算还具有性质：任何数与自身异或的结果为0，且任何数与0异或是其本身。因此，当字符串 s 和 t 中的相同字符多次出现时，这些字符将彼此抵消（即两次异或后结果为0），最终只剩下未匹配的额外字符。这保证了即使字符重复出现，异或操作仍能正确找出添加的字符。
如果字符串 t 中包含不止一个额外的字母，该方法将无法正确工作。因为异或运算将找出所有额外字符的异或结果，而不是单独的字符。若 t 中有多个不同的新增字符，异或结果将是这些字符的组合，无法再分辨出各个独立的字符。因此，这种方法仅适用于 t 中只有一个额外字符的情况。
在实际的异或操作中，遇到溢出或编码错误的可能性非常低。字符在Python中通常表示为Unicode，转换为ASCII值（或Unicode代码点）时，这些值通常适合存储在标准整数类型中。由于整数在Python中具有动态大小，即使结果超出了常规整型范围，Python也能够处理这种情况而不会发生溢出。因此，使用异或操作处理字符ASCII码在技术上是安全的。