LeetCode 0383. 赎金信：计数

【LetMeFly】383.赎金信：计数

力扣题目链接：https://leetcode.cn/problems/ransom-note/

给你两个字符串：

ransomNote

和

magazine

，判断

ransomNote

能不能由

magazine

里面的字符构成。

如果可以，返回

true

；否则返回

false

。

magazine

中的每个字符只能在

ransomNote

中使用一次。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

方法一：计数

使用一个大小为

     26 
    
   
  
    26 
   
  
26的整数数组 
 
  
   
   
     c 
    
   
     n 
    
   
     t 
    
   
  
    cnt 
   
  
cnt， 
 
  
   
   
     c 
    
   
     n 
    
   
     t 
    
   
     [ 
    
   
     i 
    
   
     ] 
    
   
  
    cnt[i] 
   
  
cnt[i]代表第 
 
  
   
   
     i 
    
   
  
    i 
   
  
i个小写字母的“可用个数”。

遍历字符串

     m 
    
   
     a 
    
   
     g 
    
   
     a 
    
   
     z 
    
   
     i 
    
   
     n 
    
   
     e 
    
   
  
    magazine 
   
  
magazine并将其字符出现次数累加；遍历字符串 
 
  
   
   
     r 
    
   
     a 
    
   
     n 
    
   
     s 
    
   
     o 
    
   
     m 
    
   
     N 
    
   
     o 
    
   
     t 
    
   
     e 
    
   
  
    ransomNote 
   
  
ransomNote并将其字符出现次数“累减”，若无次数可减，则返回

false

。

遍历完未返回

false

，则返回

true

。

• 时间复杂度 O ( l e n ( r a n s o m N o t e ) + l e n ( m a g a z i n e ) ) O(len(ransomNote) + len(magazine)) O(len(ransomNote)+len(magazine))
• 空间复杂度 O ( C ) O(C) O(C)，其中 C = 26 C=26 C=26

AC代码

C++

classSolution{public:boolcanConstruct(string ransomNote, string magazine){int cnt[26]={0};for(char c : magazine){
            cnt[c -'a']++;}for(char c : ransomNote){if(!cnt[c -'a']){returnfalse;}
            cnt[c -'a']--;}returntrue;}};

Python

classSolution:defcanConstruct(self, ransomNote:str, magazine:str)->bool:
        cnt =[0]*26for c in magazine:
            cnt[ord(c)-97]+=1for c in ransomNote:ifnot cnt[ord(c)-97]:returnFalse
            cnt[ord(c)-97]-=1returnTrue

同步发文于CSDN，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/135438384