说明

给你一个字符串 $s$和一个字符串列表 $wordDict$ 作为字典。请你判断是否可以利用字典中出现的单词拼接出$s$。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

输入格式

第一行一个字符串$s$

第二行一个整数$n$,字典的单词个数

第三行，字典单词

输出格式

输出只有一行，一个单词true或者false

样例

leetcode
2
leet code

true

applepenapple
2
apple pen

true

catsandog
5
cats dog sand and cat

false

提示：

$1 \leqslant s.length \leqslant 300$

$1 \leqslant wordDict$中单词个数 $\leqslant 1000$

$1 \leqslant wordDict[i].length \leqslant 20$

$s$ 和 $wordDict[i]$ 仅有小写英文字母组成

$wordDict$ 中的所有字符串互不相同

来源

LeetCode 139