前言
本系列文章为《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
}