Algorithm - crossword puzzles (hash table optimization)
During the Lantern Festival, the daily question is as follows:
A foreign friend has designed an English version of a crossword puzzle game based on Chinese crossword puzzles. Please guess. The puzzle of a word puzzle is given in the form of a string. If a word word meets the following two conditions, it can be counted as the answer:
The word word word contains the first letter of the puzzle.
Every letter in the word word can be found in the puzzle. For example, if the answer of a word puzzle is "abcdefg", the word that can be used as the answer is "faced",
"Cage" and "baggage"; Neither "beefed" (excluding the letter "a") nor "based" (in which "s" does not appear in the puzzle) can be used as the answer.
Returns an answer array answer. Each element answer[i] in the array is the number of words in the given word list that can be used as the answer corresponding to the puzzle puzzle [i].
- Example: Enter: words=
["aaaa","asas","able","ability","actt","actor","access"], puzzles =
["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]
Output: [1,1,3,2,4,0]
Explanation: one word can be used as the answer to "above YZ": "aaaa"
One word can be used as the answer to "abrodyz": "aaaa"
Three words can be used as the answer to "absolute": "aaaa", "asas", "able"
Two words can be used as the answer to "absoryz": "aaaa", "asas" four words can be used as "actresz"
Answer: "aaaa", "asas", "actt", "access" no words can be used as "gaswxyz"
Because none of the words in the list contain the letter 'g'. - Source: LeetCode link: https://leetcode-cn.com/problems/number-of-valid-words-for-each-puzzle
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source *.
One solution is as follows: hash table signature matching method, subset using depth first search
(the source code is not carefully annotated. I try to annotate it, because the big guy's code logic is very clear and suitable for others to learn.)
Code source: Li Kou user: verygoodlee
Infringement must be deleted
class Solution { public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) { //Create hash table Map<Integer, Integer> map = new HashMap<>(); for (String word : words) { //Traversal words character array int key = 0; for (char ch : word.toCharArray()) key |= 1 << ch - 'a';//Add the ASCII code of each letter in each word, and then perform bit or operation with 1 to generate a unique key value, | = bitwise OR operation, < < shift ch-'a 'bit to the left //Put the key represented by the corresponding word into the hash table, and the value is unified as 1 map.put(key, map.getOrDefault(key, 0) + 1); } List<Integer> res = new ArrayList<>(puzzles.length); for (String p : puzzles) { //Traversing the puzzle character array char[] puzzle = p.toCharArray(); res.add(dfs(puzzle, 1, map, 1 << puzzle[0] - 'a'));// First character required } return res; } public int dfs(char[] puzzle, int idx, Map<Integer, Integer> map, int key) { if (idx == puzzle.length) return map.getOrDefault(key, 0); // Characters other than the first character can be selected or not return dfs(puzzle, idx + 1, map, key) + dfs(puzzle, idx + 1, map, key | 1 << puzzle[idx] - 'a'); //The former returns map directly after dfs recursion Getordefault (1 < < puzzle[0] - [a ', 0). If the map contains the key of the initial letter of puzzle[0], 1 is returned, indicating that a word can be used as the answer to the puzzle //The latter dfs recurses every letter in the puzzle, takes the ASCII code value of the letters that do not appear repeatedly in the puzzle, obtains the key value of the puzzle, and uses map Getordefault (key, 0) to find out whether there are the same keys in the map. If they are the same, return value=1 } }
Summary:
1. In the compressed state, calculate the hash value of word (mode string) and put it into the map. The value is 1
2. Match the hash value, where the first letter must be selected,