大家好，我是 @负雪明烛。👈👈 点击关注，优质题解不间断。

题目大意

判断 ransom 能否由 magazines 的字符构成，也就是说是否是子集。

解题方法

理解题意很关键，这个是说从 magazine 中取出几个元素排列组合能够摆成 ransomNote，所以可以说 ransomNote 是 magazine 的子集。

字符串是否包含/子集的问题，统统用统计词频来做。既然是子集，那么 ransomNote 中每个字符出现的次数都应该小于等于该字符在 magazine 出现的次数。

统计词频有两种方法：哈希表（字典）或者数组。

哈希表（字典）

下面是 Python 解法，可以直接用 Counter 统计词频。

然后判断 ransomNote 的每个字符出现次数都小于等于其在 ransomNote 的出现次数。

  1. class Solution:
  2.     def canConstruct(self, ransomNote: str, magazine: str) -> bool:
  3.         noteCount = collections.Counter(ransomNote)
  4.         magaCount = collections.Counter(magazine)
  5.         for note in noteCount:
  6.             if magaCount[note] < noteCount[note]:
  7.                 return False
  8.         return True
  • 时间复杂度：$O(N)$
  • 空间复杂度：$O(N)$

    数组

    因为题目中说了只包含了小写字母，所以可以用有 26 个位置的数组，保存字符出现的次数。

如果使用类似于上面哈希表（字典）的解法，那么需要两个数组。

其实可以用一个数组就够了：

  • 先遍历 magazine 的字符，使其在数组中对应位置++；
  • 然后再遍历 ransomNote 的字符，使其在数组中对应位置—；
    • 如果在发现 — 之后，元素出现的个数小于 0 了，则说明该字符在 magazine 中出现的频率小于在 ransomNote 出现的频率，返回 False。
  1. public class Solution {
  2.     public boolean canConstruct(String ransomNote, String magazine) {
  3.         if(ransomNote.length() > magazine.length())
  4.             return false;
  5.         int []chars= new int[26];
  6.         for(int i=0; i< magazine.length(); i++){
  7.             chars[magazine.charAt(i)- 'a']++;
  8.         }
  9.         for(int i=0; i< ransomNote.length(); i++){
  10.             chars[ransomNote.charAt(i)- 'a']--;
  11.             if(chars[ransomNote.charAt(i)- 'a'] < 0){
  12.                 return false;
  13.             }
  14.         }
  15.         return true;
  16.     }
  17. }
  • 时间复杂度：$O(N)$
  • 空间复杂度：$O(N)$

总结

  1. 这个题依然不难，12 月持续了 Easy 题目的路线，每个 Easy 题目其实都是在练一个小知识点。
  2. 在评论区里面打卡吧！

我是 @负雪明烛 ，刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。