下面是 LeetCode 139「单词拆分」的 JavaScript 实现提供动态规划和记忆化 DFS两种解法。思路判断字符串 s 能否拆分为字典 wordDict 中的一个或多个单词。用 Set 存储字典以加速查找。方法一动态规划推荐dp[i] 表示 s 的前 i 个字符能否被成功拆分。/** * param {string} s * param {string[]} wordDict * return {boolean} */varwordBreakfunction(s,wordDict){constwordSetnewSet(wordDict);constns.length;constdpnewArray(n1).fill(false);dp[0]true;// 空字符串默认可拆分for(leti1;in;i){for(letj0;ji;j){// 若前缀 s[0..j) 可拆分且 s[j..i) 在字典中if(dp[j]wordSet.has(s.slice(j,i))){dp[i]true;break;}}}returndp[n];};方法二记忆化 DFS从位置 start 开始尝试切分用 memo 缓存结果避免重复计算。/** * param {string} s * param {string[]} wordDict * return {boolean} */varwordBreakfunction(s,wordDict){constwordSetnewSet(wordDict);constmemonewMap();// 记录 start 位置是否可拆分constdfs(start){if(starts.length)returntrue;if(memo.has(start))returnmemo.get(start);for(letendstart1;ends.length;end){constwords.slice(start,end);if(wordSet.has(word)dfs(end)){memo.set(start,true);returntrue;}}memo.set(start,false);returnfalse;};returndfs(0);};复杂度分析方法 时间复杂度 空间复杂度动态规划 O(n²) O(n)记忆化 DFS O(n²)最坏 O(n)其中 n s.length。s.slice 的时间复杂度为 O(k)但通常认为字典查找为 O(1)整体仍在 O(n²) 级别。建议面试中优先写动态规划逻辑清晰、不易出错若想展示递归思维可写记忆化 DFS。