题解

题面描述

给定一个字符串$s$`和一个字符串列表$wordDict$作为字典，要求判断是否可以利用字典中出现的一个或多个单词拼接出字符串$s$。
注意：

• 不要求字典中出现的单词全部都使用。
• 字典中的单词可以重复使用。

例如，

Leetcode 86.单词拆分-原题链接

题目内容

给你一个字符串 $s$ 和一个字符串列表 $wordDict$ 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 $s$ 则返回 $true$。

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

输入描述

第一行一个字符串$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$中的所有字符串互不相同