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)``。