问题描述

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

格式

输入

输入为一个字符串 s 和一个字符串列表 wordDict。

输出

如果可以利用字典中的单词拼接出 s，则返回 true；否则返回 false。

样例

示例 1

leetcode
leet  code

true

解释：返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2

applepenapple
apple  pen

true

解释：返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。注意，可以重复使用字典中的单词。

示例 3

catsandog 
cats dog sand and  cat

false

提示

• 1≤s.length**≤**300
• 1≤wordDict.length**≤**1000
• 1≤wordDict[i].length≤20
• s 和 wordDict[i] 仅由小写英文字母组成
• wordDict 中的所有字符串互不相同