题目
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
输入: s = "applepenapple", wordDict = ["apple", "pen"] 输出: true 解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。 注意，你可以重复使用字典中的单词。
题解
第一种
首先，定义一个长度为len的数组dp，用于记录字符串s的前i个字符能否被拆分成若干个在字典中出现过的单词。接下来遍历字符串s的前i个字符，假设当前处理到了第i个字符，则：如果s的前i个字符是一个在字典中出现过的单词，则令dp[i]为true。如果s的前i个字符不是一个在字典中出现过的单词，则需要分别考虑以第j个字符为结尾、第i个字符为开头的子串subCur，其中j的范围从0到i。对于每个子串subCur，只有当subCur是一个在字典中出现过的单词，且dp[j-1]为true，即s的前j-1个字符可以被拆分成若干个在字典中出现过的单词，才能令dp[i]为true。最终返回dp[len-1]的值，即整个字符串s是否可以被拆分成若干个在字典中出现过的单词
var wordBreak = function (s, wordDict) { let len = s.length let dp = new Array(len).fill(false) for (let i = 0; i < len; i++) { let cur = s.substring(0, i + 1) if (wordDict.indexOf(cur)>-1) { dp[i] = true } else { for (let j = 0; j <= i; j++) { let subCur = s.substring(j, i + 1) dp[i] = dp[i] || (wordDict.indexOf(subCur)>-1 && dp[j - 1]) } } } return dp[len - 1] };
第二种
定义一个长度为 n+1 的数组 dp，其中 dp[i] 表示前 i 个字符是否可以拆分成 wordDict 中的单词。首先要将 wordDict 转化为一个 Set，方便后面的查找操作。初始化 dp[0] 为 true，因为空字符串肯定可以由 wordDict 中的单词组成。接下来是动态转移方程，对于每一个 i，都在从 0 到 i-1 的范围内进行循环。如果 dp[j] 为 true，且 s 的子串从 j 开始、长度为 i-j 的子串也在 wordDict 中出现，则将 dp[i] 设为 true 并跳出内层循环，因为已经找到一种拆分方案了。最后返回 dp[n] 即可，表示整个字符串是否可以被拆分成 wordDict 中的单词
var wordBreak = function(s, wordDict) { const n = s.length; const wordDictSet = new Set(wordDict); const dp = new Array(n+1).fill(false); dp[0] = true; for(let i = 1;i<=n;i++){ for(let j = 0;j<i;j++){ if(dp[j] && wordDictSet.has(s.substr(j,i-j))){ dp[i] = true; break; } } } return dp[n]; };
