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
}

⬅️上一页

下一页➡️