94 - 赎金信

题目

给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串ransom能不能由第二个字符串magazines里面的字符构成。如果可以构成，返回 true ；否则返回 false。

(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。)

注意：

你可以假设两个字符串均只含有小写字母。

canConstruct("a", "b") -> false canConstruct("aa", "ab") -> false canConstruct("aa", "aab") -> true

解答

怎么和两个数组的交集那么像呢。。建一个哈希表咯

hash

var canConstruct = function (ransomNote, magazine) {
  let hash = new Map()
  for (let i = 0; i < magazine.length; i++) {
    if (hash.has(magazine[i])) {
      hash.set(magazine[i], hash.get(magazine[i]) + 1)
    } else {
      hash.set(magazine[i], 1)
    }
  }
  for (let i = 0; i < ransomNote.length; i++) {
    const element = ransomNote[i];
    if (!hash.has(element)) {
      return false
    }
    if (hash.get(element) > 1) {
      hash.set(element, hash.get(element) - 1)
    } else {
      hash.delete(element)
    }
  }
  return true
};

Runtime: 76 ms, faster than 80.83% of JavaScript online submissions for Ransom Note.

Memory Usage: 37.1 MB, less than 100.00% of JavaScript online submissions for Ransom Note.

func canConstruct(ransomNote string, magazine string) bool {
    hash := make(map[rune]int)
    for _, value := range magazine {
        if _, ok := hash[value]; ok {
            hash[value]++
        } else {
            hash[value] = 1
        }
    }
    for _, value := range ransomNote {
        if val, ok := hash[value]; ok {
            if val > 1 {
                hash[value]--
            } else {
                delete(hash, value)
            }
        } else {
            return false
        }
    }
    return true
}

Runtime: 16 ms, faster than 38.93% of Go online submissions for Ransom Note.

Memory Usage: 4.3 MB, less than 100.00% of Go online submissions for Ransom Note.

用数组存

var canConstruct = function (ransomNote, magazine) {
  let data = []
  for (let i = 0; i < 26; i++) {
    data[i] = 0
  }
  for (let i = 0; i < magazine.length; i++) {
    data[magazine[i].charCodeAt() - 97]++
  }
  for (let i = 0; i < ransomNote.length; i++) {
    if (data[ransomNote[i].charCodeAt() - 97] === 0) {
      return false
    } else {
      data[ransomNote[i].charCodeAt() - 97]--
    }
  }
  return true
};

Runtime: 60 ms, faster than 98.00% of JavaScript online submissions for Ransom Note.

Memory Usage: 36.7 MB, less than 100.00% of JavaScript online submissions for Ransom Note.

func canConstruct(ransomNote string, magazine string) bool {
    data := [26]rune{}
    for _, value := range magazine {
        data[value-97]++
    }w
    for _, value := range ransomNote {
        if data[value-97] == 0 {
            return false
        } else {
            data[value-97]--
        }
    }
    return true
}

Runtime: 4 ms, faster than 94.70% of Go online submissions for Ransom Note.

Memory Usage: 4.3 MB, less than 100.00% of Go online submissions for Ransom Note.