题目描述
With respect to a given puzzle string, a word is valid if both the following conditions are satisfied:
- word contains the first letter of puzzle.
- For each letter in word, that letter is in puzzle.
For example, if the puzzle is “abcdefg”, then valid words are “faced”, “cabbage”, and “baggage”, while invalid words are “beefed” (does not include ‘a’) and “based” (includes ’s' which is not in the puzzle). Return an array answer, where answer[i] is the number of words in the given word list words that is valid with respect to the puzzle puzzles[i].
Example 1:
Input: words = [“aaaa”,“asas”,“able”,“ability”,“actt”,“actor”,“access”], puzzles = [“aboveyz”,“abrodyz”,“abslute”,“absoryz”,“actresz”,“gaswxyz”]
Output: [1,1,3,2,4,0]
Explanation: 1 valid word for “aboveyz” : “aaaa” 1 valid word for “abrodyz” : “aaaa” 3 valid words for “abslute” : “aaaa”, “asas”, “able” 2 valid words for “absoryz” : “aaaa”, “asas” 4 valid words for “actresz” : “aaaa”, “asas”, “actt”, “access” There are no valid words for “gaswxyz” cause none of the words in the list contains letter ‘g’.
Example 2:
Input: words = [“apple”,“pleas”,“please”], puzzles = [“aelwxyz”,“aelpxyz”,“aelpsxy”,“saelpxy”,“xaelpsy”]
Output: [0,1,3,2,0]
Constraints:
- 1 <= words.length <= 10^5
- 4 <= words[i].length <= 50
- 1 <= puzzles.length <= 10^4
- puzzles[i].length == 7
- words[i] and puzzles[i] consist of lowercase English letters.
- Each puzzles[i] does not contain repeated characters.
题目分析
这里根据题目的hint，需要用到bit-mask，由于word，puzzle均为小写字母构成，那我们就可以将word和puzzle按照以下规则转换为一个int:
高位 低位
0 0 0 0 0 ... 0 1 1
... c b a
这样，对于题目中要求的2个条件:
- word要包含puzzle的首字母
- word中的所有字母要在puzzle中
我们都可以通过位运算进行表达；假设word和puzzle转换后的mask分别为m1，m2，puzzle的首字母转换后为first， 则有:
1. 若word含有puzzle首字母，则有 m1 & first > 0
2. 若word中所有字符都在puzzle中，则有 m1 | m2 == m2
综上，我们可以得到初始解法
初始解法
// hint: bit-masks
func findNumOfValidWords(words []string, puzzles []string) []int {
ans := make([]int, len(puzzles))
wordbits := make([]int, len(words))
// 将words转换为对应的bit-mask
for i := 0; i < len(words); i++ {
wordbits[i] = transfer2bit(words[i])
}
for i := 0; i < len(puzzles); i++ {
// puzzle[i]的bit-mask
pb := transfer2bit(puzzles[i])
// 首字母的bit-mask
firstLetter := 1 << int(puzzles[i][0]-'a')
for _, v := range wordbits {
// word含有puzzle的首字母 且 所有字符都在puzzle中
if v&firstLetter > 0 && v|pb == pb {
ans[i]++
}
}
}
return ans
}
func transfer2bit(s string) int {
bs := []byte(s)
ans := 0
// a对应最低位，b对应次低位，以此类推，构建string的bit-mask
for _, v := range bs {
ans |= 1 << int(v-'a')
}
return ans
}
优化解法
初始解法提交AC后，耗时较多，查看排名靠前的解法，发现其利用了puzzle中单词固定长度为7，比较短的特性，从而大幅缩短比较时间；
另外，也利用map去实现统计好具有相同bit-mask的word数量，避免重复比较
具体解法如下:
// hint: bit-masks
func findNumOfValidWordsV2(words []string, puzzles []string) []int {
m := make(map[int]int)
// 统计words中相同bit-mask的频次
for i := 0; i < len(words); i++ {
m[transfer2bit(words[i])]++
}
ans := make([]int, len(puzzles))
for i := 0; i < len(puzzles); i++ {
mask := transfer2bit(puzzles[i])
firstLetter := 1 << int(puzzles[i][0]-'a')
submask := mask
for submask != 0 {
// 含有puzzle首字母
if submask&firstLetter > 0 {
// 如果该submask在m中不存在，也不影响，m[submask]为0
ans[i] += m[submask]
}
// 通过减1与原mask进行与运算，得到mask中为1的不同位的所有组合
// 这样就获得了所有可能的submask的组合情况
submask = (submask - 1) & mask
}
}
return ans
}
func transfer2bit(s string) int {
bs := []byte(s)
ans := 0
// a对应最低位，b对应次低位，以此类推，构建string的bit-mask
for _, v := range bs {
ans |= 1 << int(v-'a')
}
return ans
}