题目内容

给定一个字符串 $s$ 和一个字典列表 wordDict，其中 wordDict 的每个元素都是一个可用单词。你需要判断能否把 $s$ 切成若干段连续子串，使每一段都恰好等于 wordDict 中的某个单词。字典中的单词不必全部使用，同一个单词也可以重复使用。

如果存在这样的切分方式，则返回 true；否则返回 false。

约束条件：

• 字符串 $s$ 的长度不超过 300。
• wordDict 中单词的数量不超过 1000。
• wordDict 中每个单词的长度不超过 20。
• $s$ 和 wordDict 中的单词均只包含小写英文字母。
• wordDict 中的所有单词互不相同。

输入描述

输入包含两个参数：

• 一个字符串 s，表示需要判断的目标字符串。
• 一个字符串列表 wordDict，表示可用的字典单词。

输出描述

返回一个布尔值。如果 s 可以被拆分成若干段，且每一段都出现在 wordDict 中，则返回 true；否则返回 false。

样例1

输入

a
a

输出

true

说明

目标字符串 $s$ 的长度为 1，它本身就是一个完整子串。

字典中包含单词 a，因此可以将 $s$ 切成 1 段 a，每一段都等于字典中的单词。

所以返回 true。

样例2

输入

ab
a

输出

false

说明

目标字符串 $s$ 为 ab。

字典中只有单词 a，如果先切出 a，剩余部分为 b，但 b 不在字典中。

因此无法将 $s$ 完全切分成若干段，答案为 false。

样例3

输入

abcd
abc ab cd

输出

true

说明

目标字符串 $s$ 可以切分为 2 段：ab 和 cd。

这两个子串都出现在字典中，所以能够完成拼接。

虽然字典中也有 abc，但这里使用 ab + cd 即可，答案为 true。

样例4

输入

abab
ab

输出

true

说明

目标字符串 $s$ 可以切分为 2 段：ab 和 ab。

每一段都等于字典中的单词 ab，因此同一个单词可以重复使用。

所以答案为 true。