You are given a dictionary of words and a target string s. Decide whether s can be written as a concatenation of one or more dictionary words. Each dictionary word may be used any number of times (including not at all), and the words must join together with nothing between them to spell exactly s.
Line 1: an integer k, the number of dictionary words.
Line 2: k space-separated dictionary words.
Line 3: the target string s.
All words and s consist only of lowercase letters a-z.
Print YES if s can be segmented into dictionary words, otherwise print NO.
s <= 1000Example 1
Input
3 ab abc cd abcd
Expected
YES
Explanation
"abcd" splits as "ab" + "cd", both in the dictionary, so YES.
Example 2
Input
2 ab cd abcde
Expected
NO
Explanation
After using "ab" and "cd" the trailing "e" cannot be matched by any word, 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 →