LeetCode 389. 找不同
题目描述
✅ 389. 找不同
题意分析
t由s打乱顺序后再添加一个小写字母得到，找出多出的那个字母。新增字母可以与s中已有字母相同，要求找的是多出的一次出现，而不是首次出现的新种类。两串对应字符的位置可能完全不同，不能逐个下标比较。题目保证差异恰好是一处额外出现，其余所有字符及次数都能配对，可以利用异或把这些配对部分抵消。
解法：异或抵消
核心思路
[!blue]
异或满足相同值相消、与零异或不变，并且可以交换与重新组合运算顺序。因此把两串的全部字符编码共同异或时，可以在逻辑上把相同编码放在一起配对，不需要实际排序。
对任何没有新增的字母，它在
s与t中次数相同，合起来就是偶数次，全部抵消为零。新增字母在t中多出现一次，即使原本就有多份，也只会在成对抵消后剩下一份。所以从零开始，依次异或
s和t的所有字符，最终编码就等于那个额外字符。该结论依赖题目保证恰好多出一个字符，不能用来判断任意两串的所有差异。小写英文字母在本题中可以直接按字符编码处理，Java 最后转为
char，Go 最后转为byte。s为空时，第一轮扫描自然跳过，仍会留下t中唯一字符的编码。
解题步骤
- 初始化异或累积值为
0。- 扫描
s的全部字符，将编码异或到累积值中。- 再扫描
t的全部字符，包括多出的最后一个位置。- 把剩余编码转换成返回字符类型。
代码实现
class Solution {
public char findTheDifference(String s, String t) {
// 把两串字符共同异或，相同字符成对抵消。
int xor = 0;
for (int i = 0; i < s.length(); i++) {
xor ^= s.charAt(i);
}
for (int i = 0; i < t.length(); i++) {
xor ^= t.charAt(i);
}
// 最后只剩多出来的字符编码。
return (char) xor;
}
}
func findTheDifference(s string, t string) byte {
// 把两串字符共同异或，相同字符成对抵消。
xor := 0
for i := 0; i < len(s); i++ {
xor ^= int(s[i])
}
for i := 0; i < len(t); i++ {
xor ^= int(t[i])
}
// 最后只剩多出来的字符编码。
return byte(xor)
}
复杂度分析
- 时间复杂度：$O(n+1)$，n 为 s 的长度，t 比它多一个字符，两串各扫描一次。
- 空间复杂度：$O(1)$，只保存异或累积值。
关键点总结
[!green]
- 两串共同抵消，字符的原始位置无关。
- 初始化为 0，不能无故多异或某个字符。
- 遍历 t 时必须包含比 s 多出的最后一个位置。
易错点总结
[!yellow]
- 只找新出现的字母种类：新增字符可能原本已存在，集合差集无法区分多出的一次出现。
- 两个循环都使用
s的长度：t多一个字符，必须完整扫描它。- 只异或
t：缺少s中的配对出现，无法保证原有字符全部抵消。- 按相同下标比较字符：题目允许打乱顺序，位置不同不代表该字符是新增的。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 136. 只出现一次的数字 | 简单 | 同样利用异或抵消成对字符值，两个字符串合起来只有新增字符出现奇数次。 |
| 242. 有效的字母异位词 | 简单 | 异位词两侧频次相同，本题额外多一个字符，可由频次差直接定位。 |
| 260. 只出现一次的数字 III | 中等 | 维护异或抵消关系定位少数异常值；本题异或两个字符串以找新增字符，该题用非零位分成两组分别抵消。 |
| 268. 丢失的数字 | 简单 | 维护异或抵消关系定位少数异常值；本题异或两个字符串以找新增字符，该题将下标与数值异或以找缺失值。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！