问题描述
给定两个仅包含小写字母的字符串 s 和 t。字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。
请找出在 t 中被添加的字母。
示例 1：
输入：s = "abcd", t = "abcde" 输出："e" 解释：'e' 是那个被添加的字母。
示例 2：
输入：s = "", t = "y" 输出："y"
解题思路
既然 t 只是 s 多了一个字符，那么两者的字符频率分布必然存在差异。我们可以用一个长度为 26 的数组来统计每个字母出现的次数。
遍历 s 时对应位置加一，遍历 t 时对应位置减一。最终，如果某个位置的计数小于零，说明该字符在 t 中多出现了一次，也就是我们要找的目标。这种方法不需要额外的哈希表，效率很高。
代码实现
class Solution {
public char findTheDifference(String s, String t) {
int[] cnt = new int[26];
// 统计 s 中字符频次
for (int i = 0; i < s.length(); ++i) {
cnt[s.charAt(i) - 'a']++;
}
// 减去 t 中字符频次，检测异常
for (int i = 0; i < t.length(); ++i) {
cnt[t.charAt(i) - 'a']--;
if (cnt[t.charAt(i) - 'a'] < 0) {
return t.charAt(i);
}
}
return ' ';
}
}
小结
这道题考察的是对字符频次的敏感度。实际开发中遇到类似的数据校验场景，这种计数法往往比排序或哈希更节省空间。动手敲一遍代码有助于理解边界情况，比如空字符串的处理。