算法题解：LeetCode 389 找不同

问题描述

给定两个仅包含小写字母的字符串 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 ' ';
    }
}

小结

这道题考察的是对字符频次的敏感度。实际开发中遇到类似的数据校验场景，这种计数法往往比排序或哈希更节省空间。动手敲一遍代码有助于理解边界情况，比如空字符串的处理。