Loading...
Loading...
Loading...
Sahil typed a message on his phone, but the space bar was broken, so all the words ran together. He has a list of m words he might have used, and each word can be used any number of times.
Print YES if the line s can be cut into pieces so that every piece is a word from the list. Otherwise print NO.
YES or NO.Example 1
Input
pencilbox 3 pen pencil box
Output
YES
It cuts as pencil + box, so the answer is YES.
Example 2
Input
cartcouponx 3 cart coupon cou
Output
NO
The last letter x is not part of any word, so the answer is NO.
Try the problem first. Open one hint at a time.
Let can[i] be true when the first i letters can be cut into words. can[0] is true: an empty start needs no words.
can[i] is true when some earlier cut point j has can[j] true and the letters from j to i form a word in the list.
Keep the words in a HashSet so each check is quick. The answer is can[n].
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor