Loading...
Loading...
Loading...
A word game stores n words. For each of q patterns, print YES if some stored word matches it and NO otherwise. A pattern has lowercase letters and dots. A dot matches exactly one letter, and the pattern must match the whole word.
Example 1
Input
3 7 bad dad mad pad bad .ad b.. b. .... c.d
Output
NO YES YES YES NO NO NO
b. is too short for any word, and no word starts with c.
Example 2
Input
1 1 a .
Output
YES
Try the problem first. Open one hint at a time.
Build a trie. A letter in the pattern follows one child, and a dot must try every child.
Use recursion and return as soon as one branch reaches the end of the pattern on a word end.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor