跳至主要內容

389. 找不同


389. 找不同

🟢   🔖  位运算 哈希表 字符串 排序  🔗 力扣open in new window LeetCodeopen in new window

题目

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 and t consist of lowercase English letters.

题目大意

给定两个字符串 st ,它们只包含小写字母。

字符串 t 由字符串 s 随机重排,然后在随机位置添加一个字母。

请找出在 t 中被添加的字母。

示例 1:

输入: s = "abcd", t = "abcde"

输出: "e"

解释: 'e' 是那个被添加的字母。

示例 2:

输入: s = "", t = "y"

输出: "y"

提示:

  • 0 <= s.length <= 1000
  • t.length == s.length + 1
  • st 只包含小写字母

解题思路

这个问题可以通过异或运算来高效解决。异或运算具有以下性质:

  • 相同的数字异或为零a ^ a = 0
  • 任何数与零异或为其本身a ^ 0 = a
  • 异或运算满足交换律和结合律,即 a ^ b ^ c = c ^ a ^ b

由于异或运算的特性,相同的字符异或会变为零,所以通过对合并后的字符串进行异或操作,所有相同的字符都将抵消,剩下的就是唯一一个未被抵消的字符,也就是被添加的字符。

  1. 将字符串 st 合并成一个字符串,然后对该字符串中的每个字符的 ASCII 值进行异或。
  2. 由于字符在 st 中都出现过一次(除非是被添加的字符),这些字符的 ASCII 值通过异或会相互抵消(变为零)。
  3. 最后剩下的就是被添加的字符,因为它在 t 中出现一次,而在 s 中没有对应的字符。
  4. 使用 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只出现一次的数字[✓]位运算 数组🟢🀄️open in new window 🔗open in new window
3146两个字符串的排列差哈希表 字符串🟢🀄️open in new window 🔗open in new window