Description

给定一个非空字符串 s 和一个包含非空单词列表的字典 ，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：拆分时可以重复使用字典中的单词。字典中没有重复的单词。

Input Format

第一行一个字符串s 和一个整数N，N代表字典中单词的个数（1 ≤ N ≤ 500 ）

第二行N个单词，字符串s和字典里每个单词长度都不超过100

Output Format

如果 s 可以被空格拆分为一个或多个在字典中出现的单词，输出true

否则输出false

leetcode 2
leet code​

true​

Hint

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]

输出: true

解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

示例 2：输入: s = "applepenapple", wordDict = ["apple", "pen"]

输出: true解释: 返回 true

因为 "applepenapple" 可以被拆分成 "apple pen apple"。

注意你可以重复使用字典中的单词。

示例 3：输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]

输出: false

Source

动态规划 串