You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

问题描述

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

输入

三行.第一行输入字符串s 第二行输入字典中单词个数n 第三行输入n个单词，用空格隔开

Output

如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 YES，否则是NO.

Samples

leetcode
2
leet code

YES

gohome
3
gos let home

NO

Limitation

字符串长度s不为空，并且不超过300个字符； 词典中单词数不超过1000；