mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-05 16:36:41 +08:00
116 lines
4.8 KiB
Markdown
116 lines
4.8 KiB
Markdown
# [1178. Number of Valid Words for Each Puzzle](https://leetcode.com/problems/number-of-valid-words-for-each-puzzle/)
|
||
|
||
|
||
## 题目
|
||
|
||
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" (doesn't include "a") and "based" (includes "s" which isn't in the puzzle).
|
||
|
||
Return an array `answer`, where `answer[i]` is the number of words in the given word list `words` that are valid with respect to the puzzle `puzzles[i]`.
|
||
|
||
**Example :**
|
||
|
||
```
|
||
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're no valid words for "gaswxyz" cause none of the words in the list contains letter 'g'.
|
||
|
||
```
|
||
|
||
**Constraints:**
|
||
|
||
- `1 <= words.length <= 10^5`
|
||
- `4 <= words[i].length <= 50`
|
||
- `1 <= puzzles.length <= 10^4`
|
||
- `puzzles[i].length == 7`
|
||
- `words[i][j]`, `puzzles[i][j]` are English lowercase letters.
|
||
- Each `puzzles[i]` doesn't contain repeated characters.
|
||
|
||
## 题目大意
|
||
|
||
外国友人仿照中国字谜设计了一个英文版猜字谜小游戏，请你来猜猜看吧。
|
||
|
||
字谜的迷面 puzzle 按字符串形式给出，如果一个单词 word 符合下面两个条件，那么它就可以算作谜底：
|
||
|
||
- 单词 word 中包含谜面 puzzle 的第一个字母。
|
||
- 单词 word 中的每一个字母都可以在谜面 puzzle 中找到。
|
||
例如，如果字谜的谜面是 "abcdefg"，那么可以作为谜底的单词有 "faced", "cabbage", 和 "baggage"；而 "beefed"（不含字母 "a"）以及 "based"（其中的 "s" 没有出现在谜面中）都不能作为谜底。
|
||
|
||
返回一个答案数组 answer，数组中的每个元素 answer[i] 是在给出的单词列表 words 中可以作为字谜迷面 puzzles[i] 所对应的谜底的单词数目。
|
||
|
||
提示：
|
||
|
||
- 1 <= words.length <= 10^5
|
||
- 4 <= words[i].length <= 50
|
||
- 1 <= puzzles.length <= 10^4
|
||
- puzzles[i].length == 7
|
||
- words[i][j], puzzles[i][j] 都是小写英文字母。
|
||
- 每个 puzzles[i] 所包含的字符都不重复。
|
||
|
||
## 解题思路
|
||
|
||
- 首先题目中两个限制条件非常关键：**puzzles[i].length == 7**，**每个 puzzles[i] 所包含的字符都不重复**。也就是说穷举每个puzzle的子串的搜索空间就是2^7=128，而且不用考虑去重问题。
|
||
- 因为谜底的判断只跟字符是否出现有关，跟字符的个数无关，另外都是小写的英文字母，所以可以用 `bitmap` 来表示单词(word)。
|
||
- 利用 `map` 记录不同状态的单词(word)的个数。
|
||
- 根据题意，如果某个单词(word)是某个字谜(puzzle)的谜底，那么 `word` 的 `bitmap` 肯定对应于 `puzzle` 某个子串的 `bitmap` 表示，且 `bitmap` 中包含 `puzzle` 的第一个字母的 `bit` 占用。
|
||
- 问题就转换为：求每一个 `puzzle` 的每一个子串，然后求和这个子串具有相同 `bitmap` 表示且 `word` 中包含 `puzzle` 的第一个字母的 `word` 的个数。
|
||
|
||
## 代码
|
||
|
||
```go
|
||
package leetcode
|
||
|
||
/*
|
||
匹配跟单词中的字母顺序，字母个数都无关，可以用bitmap压缩
|
||
1. 记录word中 利用map记录各种bit标示的个数
|
||
2. puzzles 中各个字母都不相同! 记录bitmap，然后搜索子空间中各种bit标识的个数的和
|
||
因为puzzles长度最长是7，所以搜索空间 2^7
|
||
*/
|
||
func findNumOfValidWords(words []string, puzzles []string) []int {
|
||
wordBitStatusMap, res := make(map[uint32]int, 0), []int{}
|
||
for _, w := range words {
|
||
wordBitStatusMap[toBitMap([]byte(w))]++
|
||
}
|
||
for _, p := range puzzles {
|
||
var bitMap uint32
|
||
var totalNum int
|
||
bitMap |= (1 << (p[0] - 'a')) //work中要包含 p 的第一个字母 所以这个bit位上必须是1
|
||
findNum([]byte(p)[1:], bitMap, &totalNum, wordBitStatusMap)
|
||
res = append(res, totalNum)
|
||
}
|
||
return res
|
||
}
|
||
|
||
func toBitMap(word []byte) uint32 {
|
||
var res uint32
|
||
for _, b := range word {
|
||
res |= (1 << (b - 'a'))
|
||
}
|
||
return res
|
||
}
|
||
|
||
//利用dfs 搜索 pussles的子空间
|
||
func findNum(puzzles []byte, bitMap uint32, totalNum *int, m map[uint32]int) {
|
||
if len(puzzles) == 0 {
|
||
*totalNum = *totalNum + m[bitMap]
|
||
return
|
||
}
|
||
//不包含puzzles[0],即puzzles[0]对应bit是0
|
||
findNum(puzzles[1:], bitMap, totalNum, m)
|
||
//包含puzzles[0],即puzzles[0]对应bit是1
|
||
bitMap |= (1 << (puzzles[0] - 'a'))
|
||
findNum(puzzles[1:], bitMap, totalNum, m)
|
||
bitMap ^= (1 << (puzzles[0] - 'a')) //异或 清零
|
||
return
|
||
}
|
||
``` |