Lt1160. 拼写单词，哈希表，桶计数

1160. 拼写单词

给你一份『词汇表』（字符串数组） words 和一张『字母表』（字符串） chars。
假如你可以用 chars 中的『字母』（字符）拼写出 words 中的某个『单词』（字符串），那么我们就认为你掌握了这个单词。
注意：每次拼写（指拼写词汇表中的一个单词）时，chars 中的每个字母都只能用一次。
返回词汇表 words 中你掌握的所有单词的 长度之和。
 示例 1：

输入：words = ["cat","bt","hat","tree"], chars = "atach"
输出：6
解释：
可以形成字符串 "cat" 和 "hat"，所以答案是 3 + 3 = 6。

示例 2：

输入：words = ["hello","world","leetcode"], chars = "welldonehoneyr"
输出：10
解释：
可以形成字符串 "hello" 和 "world"，所以答案是 5 + 5 = 10。

提示：

1. 1 <= words.length <= 1000
2. 1 <= words[i].length, chars.length <= 100
3. 所有字符串中都仅包含小写英文字母

思路

哈希表

暴力，哈希表计数，char 对应的 map 和当前字符 map 相减，看 word 是不是存在不存在的字符，以及数量是否可拼写

双重遍历

word 求 map 是不必要的，一次遍历即可出结果，使用双重循环优化

桶计数

因为只有 26 个字母，可以使用桶计数。大大节省时间空间复杂度，双 99%。

解答

/**
 * @param {string[]} words
 * @param {string} chars
 * @return {number}
 */
var countCharacters = function (words, chars) {
  const getMap = (s) => {
    const map = {};
    for (const char of s) map[char] ? map[char]++ : (map[char] = 1);
    return map;
  };
  const calculateMap = (wordMap, charMap) => {
    for (const key in wordMap) {
      if (!charMap[key]) return false;
      charMap[key] -= wordMap[key];
      if (charMap[key] < 0) return false;
    }
    return true;
  };
  const charMap = getMap(chars);
  let res = 0;
  for (const word of words) {
    const tempMap = Object.assign({}, charMap);
    res += calculateMap(getMap(word), tempMap) ? word.length : 0;
  }
  return res;
};

双重循环

/**
 * @param {string[]} words
 * @param {string} chars
 * @return {number}
 */
var countCharacters = function (words, chars) {
  const getMap = (s) => {
    const map = {};
    for (const char of s) map[char] ? map[char]++ : (map[char] = 1);
    return map;
  };

  const charMap = getMap(chars);
  let res = 0;
  for (const word of words) {
    const tempMap = Object.assign({}, charMap);
    let flag = true;
    for (const arr of word) {
      if (!tempMap[arr]) {
        flag = false;
        break;
      }
      tempMap[arr] -= 1;
    }
    if (flag) res += word.length;
  }
  return res;
};

桶计数

/**
 * @param {string[]} words
 * @param {string} chars
 * @return {number}
 */
var countCharacters = function (words, chars) {
  let res = 0;
  const arr = new Array(26).fill(0);
  for (let i = 0; i < chars.length; i++) arr[chars.charCodeAt(i) - 97]++;
  for (const word of words) {
    const tempArr = arr.concat();
    let flag = true;
    for (let i = 0; i < word.length; i++) {
      if (!tempArr[word.charCodeAt(i) - 97]) flag = false;
      tempArr[word.charCodeAt(i) - 97]--;
    }
    if (flag) res += word.length;
  }
  return res;
};