前言
本系列文章为《leetcode》刷题笔记。
题目位置：拼写单词
题集：LeetCode
项目位置：我的Github项目
题目
给你一份『词汇表』（字符串数组） 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
所有字符串中都仅包含小写英文字母
思路
如上图，这是一题hash table的题目，非常简单，先用一个map统计chars中的字母数量，然后遍历给的字符串数组，逐个统计，对比即可。
统计chars中的字母数量（int类型自动初始化为0）
cmap := make(map[uint8]int) for i := 0; i < len(chars); i++ { cmap[chars[i]] ++ }
遍历单词集合
for i := 0; i < len(words); i++ {
map拷贝（原理是序列化成json，再反序列化回来）
ExtractInto(cmap, &tmpMap)
遍历单词中的每个字母, 只要没在chars的字典中出现就判断失败，一旦出现就让当前字符字典数量--
j := 0 for ; j < len(words[i]); j++ { if tmpMap[words[i][j]] <= 0 { break } tmpMap[words[i][j]] -- }
如果j等于了当前单词长度，说明所有字母都包含在里面，就统计上。
if j == len(words[i]) { count += len(words[i]) }
可惜啊。。
估计是map本身寻找hash位置耗时，以及map拷贝耗时优化一下代码，把map转换成数组。
长度为26个字母，下标就是0-25，也就是a-a到z-a。
详细代码如下一节优化后。
代码
优化前
Go
func countCharacters(words []string, chars string) int { cmap := make(map[uint8]int) for i := 0; i < len(chars); i++ { cmap[chars[i]] ++ } count := 0 tmpMap := make(map[uint8]int) for i := 0; i < len(words); i++ { ExtractInto(cmap, &tmpMap) j := 0 for ; j < len(words[i]); j++ { if tmpMap[words[i][j]] <= 0 { break } tmpMap[words[i][j]] -- } if j == len(words[i]) { count += len(words[i]) } } return count } /* 把interface类型转换成我们想要的struct类型 这个通用方法可以转换成任意一个想要的类型 */ func ExtractInto(source interface{}, to interface{}) error { b, err := json.Marshal(source) if err != nil { return err } err = json.Unmarshal(b, to) return err }
优化后
Go
//优化后 func countCharacters(words []string, chars string) int { var byteCount [26]int for _, char := range chars { byteCount[char-'a']++ } ret := 0 for _, word := range words { bc, match := byteCount, true for _, char := range word { if bc[char-'a'] <= 0 { match = false break } bc[char-'a']-- } if match { ret += len(word) } } return ret }
