文章目录

• 题目
• • 标题和出处
  • 难度
  • 题目描述
  • • 要求
    • 示例
    • 数据范围
• 解法
• • 思路和算法
  • 代码
  • 复杂度分析

题目

标题和出处

标题：赎金信

出处：383. 赎金信

难度

2 级

题目描述

要求

给你两个字符串 ransomNote\texttt{ransomNote}ransomNote 和 magazine\texttt{magazine}magazine，如果 ransomNote\texttt{ransomNote}ransomNote 能由 magazine\texttt{magazine}magazine 构成，返回 true\texttt{true}true，否则返回 false\texttt{false}false。

magazine\texttt{magazine}magazine 中的每个字符只能在 ransomNote\texttt{ransomNote}ransomNote 中使用一次。

示例

示例 1：

输入：ransomNote="a",magazine="b"\texttt{ransomNote = "a", magazine = "b"}ransomNote = "a", magazine = "b"
输出：false\texttt{false}false

示例 2：

输入：ransomNote="aa",magazine="ab"\texttt{ransomNote = "aa", magazine = "ab"}ransomNote = "aa", magazine = "ab"
输出：false\texttt{false}false

示例 3：

输入：ransomNote="aa",magazine="aab"\texttt{ransomNote = "aa", magazine = "aab"}ransomNote = "aa", magazine = "aab"
输出：true\texttt{true}true

数据范围

• 1≤ransomNote.length,magazine.length≤105\texttt{1} \le \texttt{ransomNote.length, magazine.length} \le \texttt{10}^\texttt{5}1≤ransomNote.length, magazine.length≤105
• ransomNote\texttt{ransomNote}ransomNote 和 magazine\texttt{magazine}magazine 由小写英语字母组成

解法

思路和算法

如果 ransomNote\textit{ransomNote}ransomNote 能由 magazine\textit{magazine}magazine 构成，则等价于任意字符在 ransomNote\textit{ransomNote}ransomNote 中出现的次数不超过该字符在 magazine\textit{magazine}magazine 中出现的次数。可以使用哈希表记录每个字符在 ransomNote\textit{ransomNote}ransomNote 和 magazine\textit{magazine}magazine 中出现的次数。

一种常规的做法是使用两个哈希表分别记录每个字符在 ransomNote\textit{ransomNote}ransomNote 和 magazine\textit{magazine}magazine 中出现的次数，分别遍历 ransomNote\textit{ransomNote}ransomNote 和 magazine\textit{magazine}magazine 并更新两个哈希表，遍历结束之后比较每个字符在两个哈希表中出现的次数。如果存在一个字符，该字符在 ransomNote\textit{ransomNote}ransomNote 中出现的次数大于在 magazine\textit{magazine}magazine 中出现的次数，则 ransomNote\textit{ransomNote}ransomNote 不能由 magazine\textit{magazine}magazine 构成，返回 false\text{false}false。如果所有字符在 ransomNote\textit{ransomNote}ransomNote 中出现的次数都小于或等于在 magazine\textit{magazine}magazine 中出现的次数，则 ransomNote\textit{ransomNote}ransomNote 能由 magazine\textit{magazine}magazine 构成，返回 false\text{false}false。

上述做法可以优化。由于 ransomNote\textit{ransomNote}ransomNote 中的每个字符都需要使用 magazine\textit{magazine}magazine 中的一个字符，因此只需要一个哈希表记录每个字符的剩余数量。首先遍历 magazine\textit{magazine}magazine 并在哈希表中记录每个字符出现的次数，然后遍历 ransomNote\textit{ransomNote}ransomNote，对于 ransomNote\textit{ransomNote}ransomNote 中的每个字符，将该字符在哈希表中的剩余数量减 111，如果该字符在哈希表中的剩余数量变成负数，则该字符在 ransomNote\textit{ransomNote}ransomNote 中出现的次数大于在 magazine\textit{magazine}magazine 中出现的次数，直接返回 false\text{false}false。如果遍历 ransomNote\textit{ransomNote}ransomNote 结束之后没有出现字符在哈希表中的剩余数量变成负数的情况，则返回 true\text{true}true。

实现方面有两点可以优化。

1. 由于这道题中的字符都是小写英语字母，因此可以使用长度为 262626 的数组代替哈希表记录每个字母的剩余次数。

2. 由于 magazine\textit{magazine}magazine 中的每个字符只能在 ransomNote\textit{ransomNote}ransomNote 中使用一次，因此只有当 ransomNote\textit{ransomNote}ransomNote 的长度不超过 magazine\textit{magazine}magazine 的长度时，ransomNote\textit{ransomNote}ransomNote 才可能由 magazine\textit{magazine}magazine 构成。如果 ransomNote\textit{ransomNote}ransomNote 的长度大于 magazine\textit{magazine}magazine 的长度，则直接返回 false\text{false}false。

代码

class Solution {public boolean canConstruct(String ransomNote, String magazine) {int ransomNoteLength = ransomNote.length(), magazineLength = magazine.length();if (ransomNoteLength > magazineLength) {return false;}int[] count = new int[26];for (int i = 0; i < magazineLength; i++) {char c = magazine.charAt(i);count[c - 'a']++;}for (int i = 0; i < ransomNoteLength; i++) {char c = ransomNote.charAt(i);count[c - 'a']--;if (count[c - 'a'] < 0) {return false;}}return true;}
}

复杂度分析

• 时间复杂度：O(n+m)O(n + m)O(n+m)，其中 mmm 是字符串 ransomNote\textit{ransomNote}ransomNote 的长度，nnn 是字符串 magazine\textit{magazine}magazine 的长度。首先遍历 magazine\textit{magazine}magazine 计算每个字符在 magazine\textit{magazine}magazine 中出现的次数并存入哈希表，然后遍历 ransomNote\textit{ransomNote}ransomNote 更新每个字符在哈希表中的剩余次数，由于每个字符的操作时间都是 O(1)O(1)O(1)，因此总时间复杂度是 O(n+m)O(n + m)O(n+m)。

• 空间复杂度：O(∣Σ∣)O(|\Sigma|)O(∣Σ∣)，其中 Σ\SigmaΣ 是字符集，这道题中字符集为全部小写英语字母，∣Σ∣=26|\Sigma| = 26∣Σ∣=26。需要使用哈希表或数组记录每个字符的剩余数量，空间为 O(∣Σ∣)O(|\Sigma|)O(∣Σ∣)。