0389. Find the Difference¶
题目信息¶
- 题号:
0389
- 难度:
Easy
- 主题:
两个字符串、重新排列、单个新增字符、重复字母
- 原题:
- 重点:
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)。