LeetCode383.赎金信

题目

383.赎金信

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

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

示例1：

输入：ransomNote = "a", magazine = "b"
输出：false
1
2

示例2：

输入：ransomNote = "aa", magazine = "ab"
输出：false
1
2

示例3：

输入：ransomNote = "aa", magazine = "aab"
输出：true
1
2

提示：

• 1 <= ransomNote.length, magazine.length <= 105
• ransomNote 和 magazine 由小写英文字母组成

代码

关键审题：magazine 中的每个字符只能在 ransomNote 中使用一次。因此，不可以使用能降重的undoreded_set容器，。可以使用unordered_multiset容器将ransomNote字符串中每个字符的ASCII码存储起来。

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        unordered_multiset<int> tmp;  // multiset容器可以存储多个值相同的元素
        for (int i = 0; i < ransomNote.length(); i++) {
            tmp.insert(ransomNote[i] - 'a');   // 将ransomNote中每个字符ASCII码存进tmp中
        }

        for (int j = 0; j < magazine.length(); j++) {
            auto iter = tmp.find(magazine[j] - 'a');  // 在哈希容器tmp中逐次找magazine中元素
            if (iter != tmp.end()) { // 成功找到
                tmp.erase(iter);
            }
        }

        if (tmp.empty()) { 
            return true;
        }
        
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

另一种解法：数组

// 时间复杂度: O(n)
// 空间复杂度：O(1)
class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int record[26] = {0};
        for (int i = 0; i < magazine.length(); i++) {
            // 通过recode数据记录 magazine里各个字符出现次数
            record[magazine[i]-'a'] ++;
        }
        for (int j = 0; j < ransomNote.length(); j++) {
            // 遍历ransomNote，在record里对应的字符个数做--操作
            record[ransomNote[j]-'a']--;
            // 如果小于零说明ransomNote里出现的字符，magazine没有
            if(record[ransomNote[j]-'a'] < 0) {
                return false;
            }
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21