0389. Find the Difference ========================= 题目信息 -------- :题号: 0389 :难度: Easy :主题: 两个字符串、重新排列、单个新增字符、重复字母 :原题: `LeetCode 0389 `_ :重点: ``t`` 包含 ``s`` 的全部字符实例并多一个字符、顺序可能完全变化、返回新增字符 题目重述 -------- 给定两个只包含小写英文字母的字符串 ``s`` 和 ``t``。字符串 ``t`` 是先把 ``s`` 的全部字符任意重新排列,再额外加入一个小写字母得到的。返回这个新增字符。 ``s`` 的长度位于 ``[0, 1000]``,``t`` 的长度恰好为 ``s.length + 1``。字符串中允许出现重复字母,因此需要比较字符实例数量,而不能只比较出现过哪些字母。新增字符可能与 ``s`` 中已有字符相同。 自建示例 -------- 原字符串包含重复字符: .. code-block:: text 输入:s = "aabb",t = "ababc" 输出:"c" 解释:t 中保留了两个 a 和两个 b,并额外多出一个 c。 空原字符串: .. code-block:: text 输入:s = "",t = "z" 输出:"z" 解释:s 没有字符,因此 t 中唯一字符就是新增字符。 异或抵消相同字符实例 ---------------------- 把 ``s`` 和 ``t`` 中的所有字符一起异或。相同字符出现两次时会互相抵消,``t`` 比 ``s`` 多出的那一个字符没有对应实例,最终只剩它。字符顺序和重复次数都不会影响这个抵消过程。 C++ 实现 -------- .. code-block:: cpp 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(difference); } }; 代码分析 -------- 异或满足交换律、结合律且 ``x ^ x == 0``,因此无须排序或维护 26 个频次。两个字符串总长度只被扫描一次,时间复杂度为 ``O(|s| + |t|)``,额外空间为 ``O(1)``。