139. 单词拆分

• 题号：139
• 来源：LeetCode
• 难度：中等
• 标签：递归 字符串 dp 哈希表
• 语言：TypeScript
• 解法：2 个
• 作者：lmliheng
• 最近更新：2026-09-27

解法一

TypeScript · O(2^n) 时间 · O(n) 空间 · 更新于 2026-09-27

递归切分所有前缀组合，未剪枝

/**
 * @difficulty medium
 * @tags 递归,字符串
 * @time O(2^n)
 * @space O(n)
 * @note 递归切分所有前缀组合，未剪枝
 * @139. 单词拆分
 */

let s = "catsanddog"
let wordDict = ["cats", "dog", "sand", "and", "cat"]

let res = 0
const recursive = (str: string) => {
    if (str.length === 0) {
        res++
        return
    }
    for (let i = 0; i < wordDict.length; i++) {

        console.log('当前i为', i, '当前str为', str)
        if (str.indexOf(wordDict[i]) === 0) {
            console.log(str.slice(wordDict[i].length))
            recursive(str.slice(wordDict[i].length))
        }
    }

}

recursive(s)
console.log(res)

源码：ts/leetcode/139. 单词拆分.ts

解法二 · TypeScript

TypeScript · O(n^2) 时间 · O(n) 空间 · 更新于 2026-09-27

dp[i] 表示前 i 个字符可拆分，Set 查子串

/**
 * @difficulty medium
 * @tags dp,字符串,哈希表
 * @time O(n^2)
 * @space O(n)
 * @note dp[i] 表示前 i 个字符可拆分，Set 查子串
 * @139. 单词拆分（解法二）
 */

let s = "catsanddog"
let wordDict = ["cats", "dog", "sand", "and", "cat"]


let set = new Set(wordDict)
let n = s.length
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] && set.has(s.substr(j, i - j))) {
            dp[i] = true;
            break;
        }
    }

}
console.log(dp)

源码：ts/leetcode/139. 单词拆分（解法二）.ts

---

在 GitHub 上查看题目所在目录：lmliheng/algorithm