1366 - 单词拆分
Time Limit : 1 秒
Memory Limit : 128 MB
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意： 不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
Input
第一行为1个字符串s，表示要拼成的字符串
第二行为1个整数n，表示wordDict的长度
以下n行，每行一个字符串，表示wordDict中的元素
Output
可以拼成输出true，否则输出false
Examples
Input
leetcode 2 leet code
Output
true
Input
applepenapple 2 apple pen
Output
true
Input
catsandog 5 cats dog sand and cat
Output
false
Hint
1 <= s.length <= 3001 <= wordDict.length <= 10001 <= wordDict[i].length <= 20s和wordDict[i]仅由小写英文字母组成wordDict中的所有字符串 互不相同