拼写单词（leetcode 1160）
文章目录
1.问题描述
给你一份『词汇表』（字符串数组） 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。 所有字符串中都仅包含小写英文字母。
2.难度等级
easy。
3.热门指数
★★★★☆
出题公司：道通智能。
4.解题思路
显然，对于一个单词 word，只要其中的每个字母的数量都不大于 chars 中对应的字母的数量，那么就可以用 chars 中的字母拼写出 word。所以我们只需要用一个哈希表存储 chars 中每个字母的数量，再用一个哈希表存储 word 中每个字母的数量，最后将这两个哈希表的键值对逐一进行比较即可。
复杂度分析：
时间复杂度：O(n)，其中 n 为所有字符串的长度和。我们需要遍历每个字符串，包括 chars 以及数组 words 中的每个单词。
空间复杂度：O(S)，其中 S 为字符集大小，在本题中 S 的值为 26（所有字符串仅包含小写字母）。程序运行过程中，最多同时存在两个哈希表，使用的空间均不超过字符集大小 S，因此空间复杂度为 O(S)。
5.实现示例
5.1 C++
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
int countWordLen(const vector<string> &words, string chars) {
unordered_map<char, int> charToCnt;
for (char c : chars) {
charToCnt[c]++;
}
int wordLen = 0;
for (string word : words) {
unordered_map<char, int> m;
for (char c : word) {
m[c]++;
}
bool cotain = true;
for (char c : word) {
if (charToCnt[c] < m[c]) {
cotain = false;
break;
}
}
if (cotain) {
wordLen += word.size();
}
}
return wordLen;
}
int main() {
auto n = countWordLen(vector<string>{"cat", "bt", "hat", "tree"}, "atach");
cout << n << endl;
n = countWordLen(vector<string>{"hello", "world", "leetcode"}, "welldonehoneyr");
cout << n << endl;
}运行输出：
6
105.2 Golang
package main
import (
"fmt"
)
func countWordLen(words []string, chars string) int {
// 统计字母表中字母出现的次数。
charToNum := make(map[rune]int, len(chars))
for _, c := range chars {
v, _ := charToNum[c]
v++
charToNum[c] = v
}
// 可拼写单词总长度。
var wordLen int
for _, s := range words {
m := make(map[rune]int, len(s))
for _, c := range s {
v, _ := m[c]
v++
m[c] = v
}
contain := true
for k, v := range m {
if charToNum[k] < v {
contain = false
break
}
}
if contain {
wordLen += len(s)
}
}
return wordLen
}
func main() {
n := countWordLen([]string{"cat", "bt", "hat", "tree"}, "atach")
fmt.Println(n)
n = countWordLen([]string{"hello", "world", "leetcode"}, "welldonehoneyr")
fmt.Println(n)
}运行输出：
6
10参考文献
腾讯云开发者
