1603: 单词拼接

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：21 Solved：10

Description

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

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

示例 1： 

输入: s = "applepenapple"   wordDict = ["apple" "pen"] 
输出: true     解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     注意，你可以重复使用字典中的单词。

示例 2： 

输入: s = "catsandog"   wordDict = ["cats" "dog" "sand" "and" "cat"] 
输出: false

Input

      输入共二行，前一行为 s，s字符串只含小写英文字母，不含空格等其它字符 。后一行为 wordDic，每一单词间空一格，单词只有小写英文字母。 

Output

      输出一行。判断单词可拼接出 s 输出 true ，否则输出 false 。

Sample Input Copy 

applepenapple
apple pen

Sample Output Copy 

true

HINT


1=<s长度<=300; 1=<wordDict长度<=1000; 1=<wordDict[i]长度<=20 。

s 和 wordDict[i]仅有小写英文字母 ; wordDict中的所有字符串互不相同 。