Loading page…
Practice problem · medium
A crossword helper lists the words that fit a gap. The player types the letters they know and a dot for each letter they do not, such as b.d.
You get the dictionary and a list of such patterns. For each pattern you must say whether at least one word fits it.
Write search_patterns(words, patterns).
words is the dictionary, in lowercase letters.patterns[i] is made of lowercase letters and dots. A dot matches any one letter. A pattern fits a word only when both have the same length.Input: words = ["bad", "dad", "mad"], patterns = ["pad", "bad", ".ad", "b.."]
Output: [0, 1, 1, 1]| Pattern | A word that fits | Answer |\n|---|---|---|\n| pad | none: no word starts with p | 0 |\n| bad | bad | 1 |\n| .ad | bad, dad or mad | 1 |\n| b.. | bad | 1 |
Input: words = ["a"], patterns = ["..", "."]
Output: [0, 1]A pattern must have the same length as the word: two dots do not fit a one-letter word.
Input: words = ["tea", "ten"], patterns = ["te", "te."]
Output: [0, 1]te is only the start of the words, so no word fits it. te. fits tea.
1 ≤ length of words ≤ 1000 and 1 ≤ length of patterns ≤ 300a to z)There can be 1,000 words and 300 patterns, so checking every word for every pattern is 300,000 checks of up to 10 letters. That is fine here, but it gets slow for a big dictionary.
A trie skips every word that already failed on an early letter. Only a dot makes the walk branch.
search_patterns · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.