题目描述
题目链接:383. Ransom Note
Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.
Each letter in the magazine string can only be used once in your ransom note.
例子
例子 1
Input: ransomNote = “a”, magazine = “b”
Output: false
例子 2
Input: ransomNote = “aa”, magazine = “ab”
Output: false
例子 3
Input: ransomNote = “aa”, magazine = “aab”
Output: true
Constraints
- You may assume that both strings contain only lowercase letters.
解题思路
这道题要求判断 ransomNote
中的字符串能否用 magazine
中的字符组成,思路比较清晰。可以用一个哈希表统计 magazine
中的出现的字符以及对应次数;再遍历一次 ransomNote
看所需字符是否满足数量即可,代码如下:
1 |
|
- 时间复杂度: O(n + m)
- 空间复杂度: O(1) 字母数量为常数