1178. 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 的个数。

代码

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 搜索 puzzles 的子空间
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
}