389. 找不同
389. 找不同
🟢 🔖 位运算
哈希表
字符串
排序
🔗 力扣
LeetCode
题目
You are given two strings s
and t
.
String t
is generated by random shuffling string s
and then add one more letter at a random position.
Return the letter that was added to t
.
Example 1:
Input: s = "abcd", t = "abcde"
Output: "e"
Explanation: 'e' is the letter that was added.
Example 2:
Input: s = "", t = "y"
Output: "y"
Constraints:
0 <= s.length <= 1000
t.length == s.length + 1
s
andt
consist of lowercase English letters.
题目大意
给定两个字符串 s
和 t
,它们只包含小写字母。
字符串 t
由字符串 s
随机重排,然后在随机位置添加一个字母。
请找出在 t
中被添加的字母。
示例 1:
输入: s = "abcd", t = "abcde"
输出: "e"
解释: 'e' 是那个被添加的字母。
示例 2:
输入: s = "", t = "y"
输出: "y"
提示:
0 <= s.length <= 1000
t.length == s.length + 1
s
和t
只包含小写字母
解题思路
这个问题可以通过异或运算来高效解决。异或运算具有以下性质:
- 相同的数字异或为零:
a ^ a = 0
。 - 任何数与零异或为其本身:
a ^ 0 = a
。 - 异或运算满足交换律和结合律,即
a ^ b ^ c = c ^ a ^ b
。
由于异或运算的特性,相同的字符异或会变为零,所以通过对合并后的字符串进行异或操作,所有相同的字符都将抵消,剩下的就是唯一一个未被抵消的字符,也就是被添加的字符。
- 将字符串
s
和t
合并成一个字符串,然后对该字符串中的每个字符的 ASCII 值进行异或。 - 由于字符在
s
和t
中都出现过一次(除非是被添加的字符),这些字符的 ASCII 值通过异或会相互抵消(变为零)。 - 最后剩下的就是被添加的字符,因为它在
t
中出现一次,而在s
中没有对应的字符。 - 使用
String.fromCharCode()
将该 ASCII 值转换成字符,并返回。
复杂度分析
- 时间复杂度:
O(n)
,其中n
是字符串s + t
的长度。我们需要遍历s + t
字符串中的每个字符,并进行异或操作,时间复杂度是线性的。 - 空间复杂度:
O(1)
,只用了常数空间来存储最终的异或结果。
代码
/**
* @param {string} s
* @param {string} t
* @return {character}
*/
var findTheDifference = function (s, t) {
// 合并字符串 s 和 t,然后对每个字符的 ASCII 值进行异或
const charCode = (s + t)
.split('')
.reduce((acc, cur) => acc ^ cur.charCodeAt(), 0);
// 返回异或结果对应的字符
return String.fromCharCode(charCode);
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
136 | 只出现一次的数字 | [✓] | 位运算 数组 | 🟢 | 🀄️ 🔗 |
3146 | 两个字符串的排列差 | 哈希表 字符串 | 🟢 | 🀄️ 🔗 |