Easy

题目描述

给你两个字符串 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 只含小写字母

解题思路

这道题有多种解法，我们来分析几种常见思路：

方法一：异或运算（推荐） 由于字符串 t 是在字符串 s 的基础上添加一个字符，我们可以利用异或运算的性质：相同的数异或为0，任何数与0异或为自身。将字符串 s 和 t 中的所有字符进行异或运算，相同的字符会抵消，最终剩下的就是新增的字符。

方法二：字符频次统计 使用哈希表统计字符串 s 中每个字符的出现次数，然后遍历字符串 t，对每个字符的计数减一。最终计数不为0的字符就是新增的字符。

方法三：ASCII码求和 计算字符串 t 和 s 中所有字符的ASCII码之和，两者的差值对应的字符就是新增的字符。

方法四：排序比较 对两个字符串排序后逐位比较，找到第一个不同的位置。

综合考虑时间和空间复杂度，异或运算是最优解法，代码简洁且效率高。

代码实现

class Solution {
public:
    char findTheDifference(string s, string t) {
        char result = 0;
        for (char c : s) {
            result ^= c;
        }
        for (char c : t) {
            result ^= c;
        }
        return result;
    }
};

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        result = 0
        for c in s:
            result ^= ord(c)
        for c in t:
            result ^= ord(c)
        return chr(result)

public class Solution {
    public char FindTheDifference(string s, string t) {
        char result = (char)0;
        foreach (char c in s) {
            result ^= c;
        }
        foreach (char c in t) {
            result ^= c;
        }
        return result;
    }
}

var findTheDifference = function(s, t) {
    let result = 0;
    for (let c of s) {
        result ^= c.charCodeAt(0);
    }
    for (let c of t) {
        result ^= c.charCodeAt(0);
    }
    return String.fromCharCode(result);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型异或运算哈希表统计ASCII求和排序比较
时间复杂度O(n)O(n)O(n)O(n log n)
空间复杂度O(1)O(1)O(1)O(1)

其中 n 为字符串长度。推荐使用异或运算解法。

相关题目