1178. Number of Valid Words for Each Puzzle #

Problem #

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.

Problem Summary #

Foreign friends designed an English version of a word-riddle guessing mini-game by imitating Chinese character riddles，please come and guess.

The clue puzzle of the word riddle is given in string form，if a word word satisfies the following two conditions，then it can be considered an answer：

• The word word contains the first letter of the clue puzzle.
• Every letter in the word word can be found in the clue puzzle. For example，if the clue of the word riddle is “abcdefg”，then words that can be answers include “faced”, “cabbage”, and “baggage”；while “beefed”（does not contain the letter “a”）and “based”（the “s” in it does not appear in the clue）cannot be answers.

Return an answer array answer，each element answer[i] in the array is the number of words in the given word list words that can be answers corresponding to the word-riddle clue puzzles[i].

Notes：

• 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 all lowercase English letters.
• The characters contained in each puzzles[i] are all unique.

Solution Approach #

• First，the two constraints in the problem are very critical：puzzles[i].length == 7，the characters contained in each puzzles[i] are all unique. That is to say，the search space for enumerating each puzzle’s substrings is 2^7=128，and there is no need to consider deduplication.
• Because judging the answer is only related to whether characters appear，and not related to the number of characters，and they are all lowercase English letters，so bitmap can be used to represent a word(word).
• Use map to record the number of words(word) in different states.
• According to the problem statement，if a certain word(word) is the answer to a certain word riddle(puzzle)，then the bitmap of word must correspond to the bitmap representation of some substring of puzzle，and the bitmap contains the bit occupation of the first letter of puzzle.
• The problem is transformed into：find every substring of each puzzle，then sum the number of words that have the same bitmap representation as this substring and whose word contains the first letter of puzzle.

Code #

package leetcode

/*
	Matching is unrelated to the letter order in the word and the number of letters，bitmap compression can be used
	1. Record in word use map to record the number of various bit representations
	2. The letters in puzzles are all different! Record bitmap，then search the sum of the numbers of various bit representations in the subspace
	   Because the maximum length of puzzles is 7，so the search space is 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 must contain the first letter of p so this bit position must be 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
}

//Use dfs to search the subspace of puzzles
func findNum(puzzles []byte, bitMap uint32, totalNum *int, m map[uint32]int) {
	if len(puzzles) == 0 {
		*totalNum = *totalNum + m[bitMap]
		return
	}
	//Does not include puzzles[0],that is the bit corresponding to puzzles[0] is 0
	findNum(puzzles[1:], bitMap, totalNum, m)
	//Includes puzzles[0],that is the bit corresponding to puzzles[0] is 1
	bitMap |= (1 << (puzzles[0] - 'a'))
	findNum(puzzles[1:], bitMap, totalNum, m)
	bitMap ^= (1 << (puzzles[0] - 'a')) //xor clear to zero
	return
}