0389. Find the Difference

题目信息

题号:

0389

难度:

Easy

主题:

两个字符串、重新排列、单个新增字符、重复字母

原题:

LeetCode 0389

重点:

t 包含 s 的全部字符实例并多一个字符、顺序可能完全变化、返回新增字符

题目重述

给定两个只包含小写英文字母的字符串 s 和 t。字符串 t 是先把 s 的全部字符任意重新排列,再额外加入一个小写字母得到的。返回这个新增字符。

s 的长度位于 [0, 1000],t 的长度恰好为 s.length + 1。字符串中允许出现重复字母,因此需要比较字符实例数量,而不能只比较出现过哪些字母。新增字符可能与 s 中已有字符相同。

自建示例

原字符串包含重复字符:

输入:s = "aabb",t = "ababc"
输出:"c"
解释:t 中保留了两个 a 和两个 b,并额外多出一个 c。

空原字符串:

输入:s = "",t = "z"
输出:"z"
解释:s 没有字符,因此 t 中唯一字符就是新增字符。

异或抵消相同字符实例

把 s 和 t 中的所有字符一起异或。相同字符出现两次时会互相抵消,t 比 s 多出的那一个字符没有对应实例,最终只剩它。字符顺序和重复次数都不会影响这个抵消过程。

C++ 实现

class Solution {
public:
    char findTheDifference(std::string s, std::string t) {
        int difference = 0;
        for (char c : s) difference ^= c;
        for (char c : t) difference ^= c;
        return static_cast<char>(difference);
    }
};

代码分析

异或满足交换律、结合律且 x ^ x == 0,因此无须排序或维护 26 个频次。两个字符串总长度只被扫描一次,时间复杂度为 O(|s| + |t|),额外空间为 O(1)。