LeetCode笔记：赎金信

#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 由小写英文字母组成

解法一

思路：

遍历字符串 ransomNote，检查每一个字符是否都在 magazine 中，因为 magazine 中的每个字符只能在 ransomNote 中使用一次，检查完需要把magazine匹配到的字符删除掉，一旦有一个匹配不到就返回 false。

代码：

/**
 * @param {string} ransomNote
 * @param {string} magazine
 * @return {boolean}
 */
var canConstruct = function (ransomNote, magazine) {
  // 遍历字符串 ransomNote
  let find = ransomNote.split("").findIndex((n) => {
    // 取得每一个 ransomNote的字符在 magazine 中的位置
    let i = magazine.indexOf(n);
    if (i > -1) {
      // 如果字符在magazine中存在，则将这个字符去除掉，防止下一次重复匹配
      // 如果一直能够匹配到，则 findIndex 返回结果 find 等于-1，即最终结果返回 true
      magazine = magazine.slice(0, i) + magazine.slice(i + 1, magazine.length);
    } else {
      // 如果字符在magazine中不存在，则不满足要求，findIndex 返回结果 find 不等于-1，即最终结果返回 false
      return true;
    }
  });
  return find === -1 ? true : false;
};

解法二

思路：

  1. 遍历 magazine，统计 magazine 每一个字母的出现次数
  2. 遍历 ransomNote，从统计结果中扣除 ransomNote 中出现的相同的字母，一旦发现 ransomNote 比 magazine 字母数量多，就返回 false

代码：

/**
 * @param {string} ransomNote
 * @param {string} magazine
 * @return {boolean}
 */
var canConstruct = function (ransomNote, magazine) {
  // 构造一个长度为26的全部填充为0的数组
  const charCount = new Array(26).fill(0);

  // 获取字母a的char code
  const aCode = "a".charCodeAt();

  // 统计magazine每一个字母的出现次数
  // 比如 "acce" 统计结果为 charCount = [1, 0, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
  for (const m of magazine) {
    charCount[m.charCodeAt() - aCode]++;
  }

  // 从上面的统计结果中扣除ransomNote中的字母
  for (const r of ransomNote) {
    charCount[r.charCodeAt() - aCode]--;

    // 一旦发现超出了magazine中的字母数量，即不符合要求
    if (charCount[r.charCodeAt() - aCode] < 0) {
      return false;
    }
  }
  return true;
};

同类型解决方案的问题请参考

LeetCode 笔记: 找不同

参考

评论