LeetCode 139. 单词拆分

Categories:

Tags:

题目描述
思路分析
1. 解法一：动态规划（推荐）
2. 解法二：记忆化搜索
相似题目

题目描述

✅ 139. 单词拆分

思路分析

解法一：动态规划（推荐）

核心思路：

本题本质是完全背包的变体：字典中的单词是”物品”（可重复使用），字符串各位置是”容量”。

状态定义：dp[i] 表示字符串前 i 个字符 s[0:i] 能否被拆分为字典中的单词。

状态转移：枚举分割点 j（0 ≤ j < i），若 dp[j] == true 且 s[j:i] 在字典中，则 dp[i] = true。

初始值：dp[0] = true，空串始终可拆分，作为边界条件。

优化：命中即 break 提前剪枝；字典用哈希集合存储，单词查找 O(1)。

复杂度分析：

时间复杂度：O(n²)，其中 n 为字符串长度，嵌套枚举 i 和 j

空间复杂度：O(n + m)，其中 n 为 dp 数组长度，m 为字典哈希表大小

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // 将字典转为哈希集合，支持 O(1) 查找
        Set<String> dict = new HashSet<>(wordDict);
        int n = s.length();
        // dp[i] 表示 s[0:i] 能否被拆分
        boolean[] dp = new boolean[n + 1];
        // 空串作为边界条件
        dp[0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                // 若前 j 个字符可拆分，且 s[j:i] 在字典中，则 dp[i] 为真
                if (dp[j] && dict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    // 命中即退出，无需继续枚举
                    break;
                }
            }
        }
        return dp[n];
    }
}

func wordBreak(s string, wordDict []string) bool {
    // 将字典转为哈希集合，支持 O(1) 查找
    dict := make(map[string]bool, len(wordDict))
    for _, word := range wordDict {
        dict[word] = true
    }

    n := len(s)
    // dp[i] 表示 s[:i] 能否被拆分
    dp := make([]bool, n+1)
    // 空串作为边界条件
    dp[0] = true

    for i := 1; i <= n; i++ {
        for j := 0; j < i; j++ {
            // 若前 j 个字符可拆分，且 s[j:i] 在字典中，则 dp[i] 为真
            if dp[j] && dict[s[j:i]] {
                dp[i] = true
                // 命中即退出，无需继续枚举
                break
            }
        }
    }

    return dp[n]
}

解法二：记忆化搜索

核心思路：

定义 dfs(i) 表示 s[i:] 能否被拆分为字典中的单词。

递归枚举 s[i:j] 作为第一个单词，若在字典中则继续递归判断 s[j:]。

用 memo 数组缓存已计算结果，避免重复计算，逻辑与 DP 等价。

终止条件：i == n 时，空串可拆分，返回 true。

复杂度分析：

时间复杂度：O(n²)，其中 n 为字符串长度，每个状态最多计算一次

空间复杂度：O(n + m)，其中 n 为递归栈及 memo 数组大小，m 为字典哈希表大小

class Solution {
    private Set<String> dict;
    // memo[i]：0 未访问，1 可拆分，-1 不可拆分
    private int[] memo;
    private String s;

    public boolean wordBreak(String s, List<String> wordDict) {
        this.s = s;
        this.dict = new HashSet<>(wordDict);
        this.memo = new int[s.length()];
        return dfs(0);
    }

    private boolean dfs(int i) {
        // 到达末尾，说明拆分成功
        if (i == s.length()) {
            return true;
        }
        // 命中缓存
        if (memo[i] != 0) {
            return memo[i] == 1;
        }
        // 枚举以 i 开头的所有前缀
        for (int j = i + 1; j <= s.length(); j++) {
            if (dict.contains(s.substring(i, j)) && dfs(j)) {
                memo[i] = 1;
                return true;
            }
        }
        memo[i] = -1;
        return false;
    }
}

func wordBreak(s string, wordDict []string) bool {
    // 将字典转为哈希集合
    dict := make(map[string]bool, len(wordDict))
    for _, word := range wordDict {
        dict[word] = true
    }

    n := len(s)
    // memo[i]：0 未访问，1 可拆分，-1 不可拆分
    memo := make([]int, n)

    var dfs func(i int) bool
    dfs = func(i int) bool {
        // 到达末尾，说明拆分成功
        if i == n {
            return true
        }
        // 命中缓存
        if memo[i] != 0 {
            return memo[i] == 1
        }
        // 枚举以 i 开头的所有前缀
        for j := i + 1; j <= n; j++ {
            if dict[s[i:j]] && dfs(j) {
                memo[i] = 1
                return true
            }
        }
        memo[i] = -1
        return false
    }

    return dfs(0)
}

相似题目

题目	难度	考察点
140. 单词拆分 II	困难	回溯 + 记忆化，输出所有方案
472. 连接词	困难	多次单词拆分判断
322. 零钱兑换	中等	完全背包，最少硬币数
279. 完全平方数	中等	完全背包变体
91. 解码方法	中等	线性 DP，逐字符决策
1048. 最长字符串链	中等	动态规划，字符串变形
127. 单词接龙	困难	BFS 最短路

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/14966021