1178. Number of Valid Words for Each Puzzle

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)的谜底,那么 wordbitmap 肯定对应于 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
}



⬅️上一页

下一页➡️

Calendar Apr 8, 2023
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者