[数据结构与算法]leetcode389. 找不同

LeetCode系列文章

一、题目描述

??给定两个字符串 $s$ 和 $t$，它们只包含小写字母。
?
??字符串 $t$ 由字符串 $s$ 随机重排，然后在随机位置添加一个字母。
?
??请找出在 $t$ 中被添加的字母。

二、示例

??输入： s = “abcd”, t = “acbed”
??输出： “e”
?
??解释： 'e’是那个被添加的字母。

三、主体思路

1、计数求解

统计字母出现的次数是最容易想到的做法：

1. 先遍历字符串 $s$，统计字符串 $s$ 中每个字母出现的次数，将统计结果记录到table中。
2. 然后再遍历字符串 $t$，对table中字母出现的次数进行抵消，如果抵消后某个字母对应出现的次数变为了负数，则说明该字母就是字符串
   $t$ 当中添加的字母。

2、通过差值求解

也可以通过计算两个字符串ASCII码的差值解题：

1. 遍历字符串 $s$，对每个字母的ASCII码值进行求和。
2. 遍历字符串 $t$，对每个字母的ASCII码值进行求和。
3. 两个总ASCII码的差值对应就是字符串 $t$ 中添加字母的ASCII码值。

3、异或运算求解

??如果我们将字符串 $t$ 和字符串 $s$ 当中的字母放在一起，那么除了字符串 $t$
当中新添加的字母以外，其他字母出现的次数都一定是偶数次，因为除了新添加的字母外，其余字母在字符串 $s$ 当中出现了几次，在字符串 $t$
当中就会对应出现几次。
?
因此我们还可以用异或操作来进行求解：

1. 遍历字符串 $s$ 和字符串 $t$，对每个字母进行异或操作。
2. 异或最终得到的字符串 $t$ 中添加的字母。

四、代码实现

1、计数求解

??在统计每个字母出现的次数时，可以选择使用map或unordered_map容器，但实际没必要，因为字符串当中只包含26个小写字母，我们可以通过直接定址法的方式将对应字母出现的次数记录到对应位置，而没有必要在底层维护一个红黑树或哈希表。
?
代码如下：

2、通过差值求解

3、异或运算求解

开发者涨薪指南

48位大咖的思考法则、工作方式、逻辑体系