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

2024-01-08 06:00:18

题目来源

力扣每日一题;题序: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;

}

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

文章来源:https://blog.csdn.net/weixin_42075274/article/details/135445379
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。