Question

1160. 拼写单词

English Version

题目描述

给你一份『词汇表』（字符串数组） 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 <= words.length <= 1000
• 1 <= words[i].length, chars.length <= 100
• 所有字符串中都仅包含小写英文字母

解法

方法一：计数

我们可以用一个长度为 $26$ 的数组 $cnt$ 统计字符串 $chars$ 中每个字母出现的次数。

然后遍历字符串数组 $words$，对于每个字符串 $w$，我们用一个长度为 $26$ 的数组 $wc$ 统计字符串 $w$ 中每个字母出现的次数，如果对于每个字母 $c$，$wc[c] \leq cnt[c]$，那么我们就可以用 $chars$ 中的字母拼写出字符串 $w$，否则我们无法拼写出字符串 $w$。如果可以拼写出字符串 $w$，那么我们就将字符串 $w$ 的长度加到答案中。

遍历结束后，即可得到答案。

时间复杂度 $(L)$，空间复杂度 $O(C)$。其中 $L$ 为题目中所有字符串的长度之和；而 $C$ 为字符集的大小，本题中 $C = 26$。

class Solution:
  def countCharacters(self, words: List[str], chars: str) -> int:
    cnt = Counter(chars)
    ans = 0
    for w in words:
      wc = Counter(w)
      if all(cnt[c] >= v for c, v in wc.items()):
        ans += len(w)
    return ans

class Solution {
  public int countCharacters(String[] words, String chars) {
    int[] cnt = new int[26];
    for (int i = 0; i < chars.length(); ++i) {
      ++cnt[chars.charAt(i) - 'a'];
    }
    int ans = 0;
    for (String w : words) {
      int[] wc = new int[26];
      boolean ok = true;
      for (int i = 0; i < w.length(); ++i) {
        int j = w.charAt(i) - 'a';
        if (++wc[j] > cnt[j]) {
          ok = false;
          break;
        }
      }
      if (ok) {
        ans += w.length();
      }
    }
    return ans;
  }
}

class Solution {
public:
  int countCharacters(vector<string>& words, string chars) {
    int cnt[26]{};
    for (char& c : chars) {
      ++cnt[c - 'a'];
    }
    int ans = 0;
    for (auto& w : words) {
      int wc[26]{};
      bool ok = true;
      for (auto& c : w) {
        int i = c - 'a';
        if (++wc[i] > cnt[i]) {
          ok = false;
          break;
        }
      }
      if (ok) {
        ans += w.size();
      }
    }
    return ans;
  }
};

func countCharacters(words []string, chars string) (ans int) {
  cnt := [26]int{}
  for _, c := range chars {
    cnt[c-'a']++
  }
  for _, w := range words {
    wc := [26]int{}
    ok := true
    for _, c := range w {
      c -= 'a'
      wc[c]++
      if wc[c] > cnt[c] {
        ok = false
        break
      }
    }
    if ok {
      ans += len(w)
    }
  }
  return
}

function countCharacters(words: string[], chars: string): number {
  const idx = (c: string) => c.charCodeAt(0) - 'a'.charCodeAt(0);
  const cnt = new Array(26).fill(0);
  for (const c of chars) {
    cnt[idx(c)]++;
  }
  let ans = 0;
  for (const w of words) {
    const wc = new Array(26).fill(0);
    let ok = true;
    for (const c of w) {
      if (++wc[idx(c)] > cnt[idx(c)]) {
        ok = false;
        break;
      }
    }
    if (ok) {
      ans += w.length;
    }
  }
  return ans;
}

class Solution {
  /**
   * @param String[] $words
   * @param String $chars
   * @return Integer
   */
  function countCharacters($words, $chars) {
    $sum = 0;
    for ($i = 0; $i < strlen($chars); $i++) {
      $hashtable[$chars[$i]] += 1;
    }
    for ($j = 0; $j < count($words); $j++) {
      $tmp = $hashtable;
      $sum += strlen($words[$j]);
      for ($k = 0; $k < strlen($words[$j]); $k++) {
        if (!isset($tmp[$words[$j][$k]]) || $tmp[$words[$j][$k]] === 0) {
          $sum -= strlen($words[$j]);
          break;
        }
        $tmp[$words[$j][$k]] -= 1;
      }
    }
    return $sum;
  }
}