A signboard printer owns a set of reusable word tiles. It wants to know whether a requested phrase (given with no separators) can be built by concatenating tiles from its dictionary, where each tile may be used any number of times and the whole phrase must be covered exactly.
Line 1: an integer k, the number of dictionary words.
Line 2: k space-separated distinct dictionary words.
Line 3: the target string s.
Print YES if s can be segmented into a sequence of dictionary words, otherwise NO.
s <= 300Example 1
Input
4 app le apple pen applepen
Expected
YES
Explanation
applepen splits as apple + pen (or app + le + pen), both using dictionary words, so YES.
Example 2
Input
5 cat cats and sand dog catsandog
Expected
NO
Explanation
No concatenation of the dictionary words spells catsandog exactly, so NO.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →