0389. 找不同 #

标签：位运算、哈希表
难度：简单

题目大意 #

给定两个只包含小写字母的字符串 s、t。字符串 t 是由 s 进行随机重拍之后，再在随机位置添加一个字母得到的。要求：找出字符串 t 中被添加的字母。

解题思路 #

字符串 t 比字符串 s 多了一个随机字母。可以使用哈希表存储一下字符串 s 中各个字符的数量，再遍历一遍字符串 t 中的字符，从哈希表中减去对应数量的字符，最后剩的那一个字符就是多余的字符。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        s_dict = dict()
        for ch in s:
            if ch in s_dict:
                s_dict[ch] += 1
            else:
                s_dict[ch] = 1

        for ch in t:
            if ch in s_dict and s_dict[ch] != 0:
                s_dict[ch] -= 1
            else:
                return ch