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

题目来源

力扣每日一题；题序：383

我的题解

方法一 哈希表

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

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

public boolean canConstruct(String ransomNote, String magazine) {
 Map<Character,Integer> need=new HashMap<>();
    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)
            return false;
    }
    return true;
}

方法二 数组

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

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

public boolean canConstruct(String ransomNote, String magazine) {
  int[] rans=new int[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)
          return false;
          
  }
  return true;

}

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