leetcode383. 赎金信

leetcode

题目描述

给你两个字符串：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 由小写英文字母组成

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/ransom-note 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

法1

哈希表:\

1. 建立map[rune]int:用于储存出现的字母与出现的次数,

m:=make(map[rune]int)

2. 遍历ransomNote,记录每个字母出现的次数并储存在map中

for _, v := range ransomNote {
  m[v]=m[v]+1
 }

3. 遍历magazine.当map中没有如何元素时返回ture,如果完全遍历magazine且map中还存在元素返回false

for _, v := range magazine {
  if m[v]>1{
   m[v]--
  }else if m[v]==1 {
   delete(m,v)
  }
  if len(m)==0 {
   return true
  }
 }

执行结果

法1

func canConstruct(ransomNote string, magazine string) bool {
 if len(ransomNote)>len(magazine) {
  return false
 }
 m:=make(map[rune]int)
 for _, v := range ransomNote {
  m[v]=m[v]+1
 }
 for _, v := range magazine {
  if m[v]>1{
   m[v]--
  }else if m[v]==1 {
   delete(m,v)
  }
  if len(m)==0 {
   return true
  }
 }
 return false
}

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 12 ms , 在所有 Go 提交中击败了 46.30% 的用户 内存消耗： 3.7 MB , 在所有 Go 提交中击败了 53.23% 的用户 通过测试用例： 128 / 128

优化

1. 用26位数组来代替map,
2. 减少一个循环,用一个循环同时遍历两个字符串;

func canConstruct(ransomNote string, magazine string) bool {
 if len(ransomNote) > len(magazine) {
  return false
 }
 a := make([]int, 26)
 for j:=0;j<len(magazine);j++ {
  a[magazine[j]-97]++
  if j<len(ransomNote) {
   a[ransomNote[j]-97]--
  }
 }
 for _, v := range a {
  if v<0 {
   return false
  }
 }
 return true
}

执行用时： 4 ms , 在所有 Go 提交中击败了 83.92% 的用户 内存消耗： 3.7 MB , 在所有 Go 提交中击败了 64.97% 的用户 通过测试用例： 128 / 128