033 · Ransom Note

My First Thoughts

这道题其实前面应该有类似的题。看到两个字符串，再看到要比较字符能不能对应上，我会想到 Valid Anagram 那种 s 和 t 的感觉。

这里可以理解成：ransomNote 需要的字符，必须都能从 magazine 里拿出来。换句话说，ransomNote 需要是 magazine 在字符数量上的一个子集。

但这里有个重点：字符是可以重复的。

所以不能只用 set。如果用 set，它只能告诉我们某个字符有没有出现过，不能告诉我们这个字符出现了几次。比如：

ransomNote = "aa"
magazine = "ab"

set(magazine) 里确实有 "a"，但 magazine 里只有一个 "a"，不够拼出 "aa"。

所以按理应该用字典更合适。思路是：

• 遍历 magazine，遇到过的字符就 +1，没遇到过的字符就先加入字典
• 再遍历 ransomNote，如果字符在字典里并且还有剩余，就把数量 -1
• 如果字符不在字典里，或者数量已经是 0，就返回 False

代码大概就是：

def canConstruct(ransomNote, magazine):
    reference = {}

    for char in magazine:
        reference[char] = reference.get(char, 0) + 1

    for char in ransomNote:
        if char not in reference or reference[char] == 0:
            return False

        reference[char] -= 1

    return True

这里不需要判断两个字符串长度相等。因为这题不是问两个字符串是不是刚好由同一批字符组成，而是问 magazine 能不能提供足够的字符给 ransomNote。magazine 多出来的字符没关系。

---

Why That Is Not Enough

这个方向已经是完整可行的解法了。真正需要小心的地方不是思路错了，而是要把“子集”理解成数量上的子集。

如果只是写：

if char in magazine:

那只是在判断“有没有”。但这题还要判断“够不够”。ransomNote 里每出现一次某个字符，就会消耗 magazine 里的一次库存。

所以最终代码里有两个动作必须配套出现：

if char not in reference or reference[char] == 0:
    return False

reference[char] -= 1

先判断还够不够，再消耗一个。这样遇到重复字符时，字典里的数量会真实减少，不会把同一个字符重复使用多次。

---

Final Idea

关键思路是：

把 magazine 看成一份字符库存；ransomNote 每需要一个字符，就从库存里扣掉一个。

第一轮遍历 magazine，建立库存：

reference = {}

for char in magazine:
    reference[char] = reference.get(char, 0) + 1

比如：

magazine = "aab"

会得到类似这样的字典：

{"a": 2, "b": 1}

第二轮遍历 ransomNote，逐个消耗：

for char in ransomNote:
    if char not in reference or reference[char] == 0:
        return False

    reference[char] -= 1

如果需要的字符不存在，或者已经用完，就说明拼不出来。只要整个 ransomNote 都能顺利扣完，说明每个字符都够用。

---

Why It Works

reference 记录的是 magazine 中每个字符还可以使用多少次。

遍历 ransomNote 时，每个字符都代表一次需求。对于当前字符，有两种失败情况：

• 字典里没有这个字符，说明 magazine 从来没有提供过它
• 字典里有这个字符，但数量是 0，说明之前已经用完了

只要出现这两种情况之一，就不可能拼出完整的 ransomNote。

如果当前字符还有剩余，就把数量减一，表示这个字符已经被用掉一次。因为每次使用都会扣库存，所以同一个 magazine 字符不会被重复使用。

当循环结束时，ransomNote 里的所有字符需求都被满足了，所以返回 True。

---

Code

def canConstruct(ransomNote, magazine):
    reference = {}

    for char in magazine:
        reference[char] = reference.get(char, 0) + 1

    for char in ransomNote:
        if char not in reference or reference[char] == 0:
            return False

        reference[char] -= 1

    return True

也可以把判断写成：

if reference.get(char, 0) == 0:
    return False

因为 get(char, 0) 在字符不存在时会返回 0。不过第一版把“不存在”和“数量为 0”分开写，也很清楚。

---

Complexity

Time	\(O(r + m)\) - r 是 ransomNote 的长度，m 是 magazine 的长度；先遍历 magazine 建库存，再遍历 ransomNote 消耗库存
Space	\(O(m)\) - 字典里最多保存 magazine 中出现过的不同字符

---

Takeaway

当题目从“某个字符有没有出现”变成“某个字符数量够不够”时，set 就不够了。把来源字符串看成库存，用字典记录数量，再随着目标字符串逐步消耗，是这类题最直接的思路。

---

← Quiz