From
Leetcode
Status
AC
Date
Apr 16, 2024
Tags
完全背包
排列
动态规划
Difficulty
中等
题面
给你一个字符串
s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 1：
示例 2：
示例 3：
提示：
1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s和wordDict[i]仅由小写英文字母组成
wordDict中的所有字符串 互不相同
思路
dp[i] = dp[j] + s[i - j]
遍历顺序：先背包后物品，因为有排列顺序