Leetcode题解之 —— 赎金信

思路

思路一(172ms)

暴力解法

  • 遍历magazine
  • 如果ransomNote中存在对应的值, 则删除
  • 返回ransomNote的剩余长度

思路二(120ms)

哈希计数法

  • cache计数ransomNote的每个字符的出现次数
  • 遍历magazine, 抵消值
    • 小于0判断
  • 遍历values()查看是否有为抵消的数

题解

  • 解法一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {string} ransomNote
 * @param {string} magazine
 * @return {boolean}
 */
var canConstruct = function(ransomNote, magazine) {
  // TODO solution 1
  ransomNote = ransomNote.split('');
  magazine = magazine.split('');

  for (const ch of magazine) {
    const where = ransomNote.indexOf(ch);

    where !== -1 && (ransomNote.splice(where, 1));
  }

  return ransomNote.length === 0;
};
  • 解法二
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @param {string} ransomNote
 * @param {string} magazine
 * @return {boolean}
 */
var canConstruct = function(ransomNote, magazine) {
  const cache = new Map();

  for (const ch of ransomNote) {
    cache.set(ch, cache.has(ch) ? cache.get(ch) + 1 : 1);
  }
  for (const ch of magazine) {
    cache.has(ch) && (cache.get(ch) > 0 && (cache.set(ch, cache.get(ch) - 1)));
  }

  for (const v of cache.values()) {
    if (v !== 0) {
      return false;
    }
  }

  return true;
};