LeetCode 472拼接单词问题：JavaScript代码单测试用例失败求助

你的代码逻辑是对的，但在处理大量长字符串的测试用例时会超时，核心原因是没有利用单词长度的顺序优化判断逻辑，同时递归DFS的方式在处理长单词时会带来额外的栈开销和重复计算。

问题分析 #

1. 原代码直接使用包含所有单词的集合进行判断，集合中存在的长单词对当前短单词的判断毫无意义，反而会增加不必要的查询成本。
2. 递归DFS的缓存虽然能减少部分重复计算，但对于超长单词来说，递归深度和子问题数量会急剧增加，导致超时。
3. 没有过滤掉无效的判断场景：比如长度小于两个最短单词长度之和的单词，不可能是拼接单词，但原代码还是会对其进行DFS判断。

优化方案 #

1. 按长度排序：先将单词按长度从小到大排序，这样处理每个单词时，所有可能的组成部分（更短的单词）都已经在集合中，避免了用长单词去判断短单词的情况，同时保证拼接的单词都是符合要求的“更短单词”。
2. 动态规划替代递归：用动态规划的迭代方式判断单个单词是否能被拼接，避免递归的栈开销，同时更高效地处理子问题。
3. 延迟加入集合：处理每个单词时，先判断它是否是拼接单词，再将其加入集合（无论是否是拼接单词，都要加入，因为它可能成为后续长单词的组成部分）。

修改后的代码 #

var findAllConcatenatedWordsInADict = function(words) {
    // 按单词长度从小到大排序，长度相同的顺序不影响
    words.sort((a, b) => a.length - b.length);
    const wordSet = new Set();
    const result = [];

    for (const word of words) {
        if (canForm(word, wordSet)) {
            result.push(word);
        }
        wordSet.add(word);
    }

    return result;
};

function canForm(word, wordSet) {
    // 集合为空时，没有单词可以用来拼接
    if (wordSet.size === 0) return false;
    const len = word.length;
    // dp[i] 表示 word 的前 i 个字符能否被集合中的单词拼接而成
    const dp = new Array(len + 1).fill(false);
    dp[0] = true; // 空前缀视为可拼接

    for (let i = 1; i <= len; i++) {
        for (let j = 0; j < i; j++) {
            // 如果前j个字符可拼接，且j到i的子串在集合中，则前i个字符可拼接
            if (dp[j] && wordSet.has(word.substring(j, i))) {
                dp[i] = true;
                break; // 找到一种方式即可，无需继续遍历
            }
        }
    }

    return dp[len];
}

优化效果说明 #

• 排序后，每个单词的判断只依赖更短的单词，完全符合题目中“至少两个更短单词组成”的要求。
• 动态规划的迭代方式避免了递归栈的开销，同时通过break提前终止内层循环，减少不必要的计算。
• 延迟加入集合的逻辑，确保判断当前单词时，集合中没有自身，避免了误判的可能（虽然题目中单词无重复，但这个逻辑更严谨）。

内容的提问来源于stack exchange，提问作者Abhishek Anand