035 · Find the Difference

My First Thoughts

继续练习字符串。这道题要找出 t 比 s 多出来的那个字符，感觉解法不止一种。

第一个想法是复用之前 004 判断 anagram 的函数。既然 t 只比 s 多一个字符，那只要试着从 t 里去掉某一个字符，剩下的部分如果正好是 s 的 anagram，那被去掉的就是答案。这是不考虑复杂度的纯思路：

def find_difference(s, t):
    for i in range(len(t)):
        candidate = t[:i] + t[i+1:]   # 去掉下标 i 的字符
        if is_anagram(candidate, s):
            return t[i]

字符串是不可变的，删掉一个下标不能直接改，所以用切片 t[:i] + t[i+1:] 拼出「去掉第 i 个字符」的新字符串。这个能做，但每次都要切片再判断 anagram，明显是 \(O(n^2)\)，只是当复用练习，不是正解。

第二个想法是计数。把 s 的字符次数记下来，再用 t 去减，最后遍历看哪个字符的次数变成了 -1，那就是多出来的字符。这个方向感觉很接近正解，甚至可能就是正解。

第三个想法是边走边消除。直接遍历 t 的每个字符，如果它在 s 里就把它从 s 删掉，如果不在就直接返回。这样遇到多出来的字符可以早点结束。逻辑上也对，但 char in s 和删除都要扫字符串，整体又退化成 \(O(n^2)\)。

---

Why That Is Not Enough

三个思路里，第一个和第三个的核心逻辑都没错，但都踩到同一个点：Python 字符串是不可变的。

想「删掉一个字符」或者「在 s 里逐个消除」，都不能在原字符串上直接改，要么靠切片重新拼一个新字符串，要么先转成 list。再加上 char in s 本身也要扫一遍，所以这两条路虽然意思对，但每一步都不便宜，很容易变成 \(O(n^2)\)。

也就是说，真正需要维护的不是一个能被删的字符串，而是一个能被减的字符计数表。这正好是第二个想法。

---

Final Idea

用一个 hash map 记录字符计数。

先遍历 s，每看到一个字符就把它的计数加一。再遍历 t，每看到一个字符就把对应计数减一。因为 t 只比 s 多了一个字符，所以减的过程中，唯一会被减到「比 s 里还多」的那个字符，就是答案。

具体判断很简单：减完之后如果某个字符的计数变成了负数，说明 t 里这个字符比 s 多，当场返回它就行，不用等遍历完再回头找。

---

Why It Works

第一个循环把 s 的字符频率存下来。第二个循环用 t 的字符逐个抵消这些频率。

如果 s 和 t 在某个字符上次数相同，它最终会被减到 0，不会出问题。而那个多出来的字符，在 s 里的计数比 t 少一次，所以减到它的时候计数会掉到 -1。题目保证 t 恰好只多一个字符，所以第一个被减成负数的字符，就是唯一的答案。

---

Code

def find_difference(s, t):
    counts = {}

    for char in s:
        counts[char] = counts.get(char, 0) + 1

    for char in t:
        counts[char] = counts.get(char, 0) - 1
        if counts[char] < 0:
            return char

---

Complexity

Time	\(O(n)\) — s 和 t 各遍历一次
Space	\(O(1)\) — 只有 26 个小写英文字母，字符种类数固定

---

Takeaway

想「删字符」「消字符」的时候，先停一下：Python 字符串不可变，每次删都在重建字符串。如果题目只关心字符出现的次数，把字符串换成一个能加减的计数表，思路不变，复杂度却从 \(O(n^2)\) 降到 \(O(n)\)。

---

← Quiz