题目描述

题目链接：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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#include <string>
#include <vector>

class Solution {
public:
    bool canConstruct(std::string ransomNote, std::string magazine) {
        std::vector<int> count(26, 0);
        for (char letter: magazine) {
            count[letter - 'a']++;
        }

        for (char letter: ransomNote) {
            count[letter - 'a']--;
            if (count[letter - 'a'] < 0) return false;
        }

        return true;
    }
};

• 时间复杂度: O(n + m)
• 空间复杂度: O(1) 字母数量为常数