LeetCode: 383 Ransom Note

Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.

Each letter in magazine can only be used once in ransomNote.

Example:

Input: ransomNote = "a", magazine = "b"
Output: false

Example:

Input: ransomNote = "aa", magazine = "ab"
Output: false

Example:

Input: ransomNote = "aa", magazine = "aab"
Output: true

问题

给定两个字符串 ransomNote 和 magazine，如果 ransomNote 可以由 magazine 中的字母构成，则返回 true，否则返回 false。

magazine 中的每个字母只能在 ransomNote 中使用一次。

解决方案

哈希表法

Approach: HashMap Counting / 哈希表计数法

This approach uses a HashMap (or a dictionary in Python) to count the occurrences of each letter in magazine. We then iterate over each letter in ransomNote to check if it can be formed using the available letters in the magazine.

这种方法使用哈希表（或 Python 中的字典）来统计 magazine 中每个字母的出现次数。然后，我们遍历 ransomNote 中的每个字母，检查是否可以用 magazine 中可用的字母来构成。

Implementation / 实现

Python

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        letter_count = {}

        for letter in magazine:
            if letter in letter_count:
                letter_count[letter] += 1
            else:
                letter_count[letter] = 1

        for letter in ransomNote:
            if letter not in letter_count or letter_count[letter] == 0:
                return False
            letter_count[letter] -= 1

        return True

Explanation / 解释

1. Initialize the HashMap / 初始化哈希表

   letter_count = {}

   • English: We initialize a HashMap letter_count to store the count of each letter in the magazine.
   • Chinese: 我们初始化一个哈希表 letter_count 来存储 magazine 中每个字母的计数。

2. Count Letters in Magazine / 统计 magazine 中的字母

   for letter in magazine:
      if letter in letter_count:
          letter_count[letter] += 1
      else:
          letter_count[letter] = 1

   • English: We iterate over each letter in magazine to populate the letter_count dictionary with the frequency of each letter.
   • Chinese: 我们遍历 magazine 中的每个字母，将每个字母的频率填入 letter_count 字典。

3. Check Ransom Note Letters / 检查 ransomNote 中的字母

   for letter in ransomNote:
      if letter not in letter_count or letter_count[letter] == 0:
          return False
      letter_count[letter] -= 1

   • English: We iterate over each letter in ransomNote and check if it exists in letter_count with a non-zero count. If any letter cannot be matched, we return False.
   • Chinese: 我们遍历 ransomNote 中的每个字母，检查它是否存在于 letter_count 中且计数不为零。如果任何字母无法匹配，我们返回 False。

4. Return True if All Letters Match / 如果所有字母匹配则返回 True

   return True

   • English: If all letters in ransomNote can be matched with magazine, we return True.
   • Chinese: 如果 ransomNote 中的所有字母都可以与 magazine 匹配，我们返回 True。

Recursive Approach / 递归方法

A recursive approach for this problem is generally not practical due to the need to track letter counts efficiently. The iterative method using a HashMap is the optimal solution.

由于需要高效地跟踪字母计数，递归方法通常不适用于这个问题。使用哈希表的迭代方法是最佳解决方案。

Complexity Analysis / 复杂度分析

• Time Complexity / 时间复杂度: O(m + n), where m is the length of magazine and n is the length of ransomNote. We traverse both strings once.
• Space Complexity / 空间复杂度: O(1), since the space used by letter_count depends on the character set, which is constant (only lowercase letters).

Key Concept / 关键概念

• HashMap Counting / 哈希表计数: This technique efficiently tracks and checks the availability of characters needed to construct the ransomNote.
• 哈希表计数: 这种技术高效地跟踪和检查构建 ransomNote 所需字符的可用性。

Summary / 总结

• English: The HashMap counting method is ideal for problems involving character frequency and availability, especially when the task involves multiple checks across different strings.
• Chinese: 哈希表计数方法非常适合处理涉及字符频率和可用性的问题，尤其是在任务涉及跨多个字符串的多次检查时。

Tips / 提示

• English: Practice using HashMaps to solve problems involving character counts, as this pattern frequently appears in coding challenges.
• Chinese: 练习使用哈希表解决涉及字符计数的问题，因为这种模式经常出现在编码挑战中。

Solution Template for Similar Questions / 提示

• English: Consider using HashMaps when you need to count and compare elements between two collections, such as strings or arrays.
• Chinese: 当你需要在两个集合（如字符串或数组）之间计数和比较元素时，考虑使用哈希表。

5 More Similar Questions / 推荐5问题

1. LeetCode 242. Valid Anagram
2. LeetCode 387. First Unique Character in a String
3. LeetCode 49. Group Anagrams
4. LeetCode 202. Happy Number
5. LeetCode 389. Find the Difference

Recommended Resources / 推荐资源

• English: Practice problems involving character frequency and string manipulation to strengthen your understanding of HashMap-based solutions.
• Chinese: 练习涉及字符频率和字符串操作的问题，以加强你对基于哈希表的解决方案的理解。

Ransom Note – Leetcode 383 – Hashmaps & Sets (Python) by Greg Hogg