2024.1.7力扣每日一题——赎金信

2024.1.7

题目来源

力扣每日一题；题序：383

我的题解

方法一 哈希表

使用哈希表记录ransomNote中所需字符的数量，然后遍历magazine并将哈希表中存在的对应的数量减一

时间复杂度：O(n+m)。n表示ransomNote的长度，m表示magazine的长度
空间复杂度：O(n)。

publicbooleancanConstruct(String ransomNote,String magazine){Map<Character,Integer> need=newHashMap<>();for(Character ch:ransomNote.toCharArray()){
        need.put(ch,need.getOrDefault(ch,0)+1);}for(Character ch:magazine.toCharArray()){if(need.containsKey(ch))
            need.put(ch,need.get(ch)-1);}for(Character key:need.keySet()){if(need.get(key)>0)returnfalse;}returntrue;}

方法二 数组

由于都是小写字母，所以可以使用数组代替哈希表
这里采用先求magazine中的各个字母的数量，然后去匹配ransomNote，这样可以在匹配的过程中判断magazine某个字符不存在或者该字符的数量不足以组成ransomNote，可以提前结束后续的计算。

时间复杂度：O(n+m)
空间复杂度：O(|S|)。|S|=26

publicbooleancanConstruct(String ransomNote,String magazine){int[] rans=newint[26];for(int i=0;i<magazine.length();i++){char ch=magazine.charAt(i);
      rans[ch-'a']++;}for(int i=0;i<ransomNote.length();i++){char ch=ransomNote.charAt(i);
      rans[ch-'a']--;if(rans[ch-'a']<0)returnfalse;}returntrue;}

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~