2025-03-20

139. 单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

这种一看就是后面的判断需要前面的条件,并且前面还可以继续拆分的题,一看就是动态规划 动态规划的基本思想可以看这篇

这题可以这样看:从最后一位,假设是leetCode,那么把e排除,看leetCod 是否能够在字典中找到对应的字符串拼接起来,同理,把d去掉,看leetCo,是不是就非常容易理解,那么可以倒着循环,也可以正着循环,反正都一样.

function wordBreak(s: string, wordDict: string[]): boolean {
    let n = s.length
    let wordDictSet = new Set(wordDict)
    let 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];
};

时间复杂度: O(n²) 进行了两层次循环(一般来说,dp的时间复杂度总会在n²上下) 空间复杂度: O(n) 使用了长度为n+1的set对象