LeetCode 140. 单词拆分 II

Categories:

题目描述
思路分析
1. 解法一：DFS + 记忆化（推荐）
相似题目

题目描述

✅ 140. 单词拆分 II

思路分析

解法一：DFS + 记忆化（推荐）

核心思路：

用 DFS 从起点尝试匹配单词，递归拼接后续结果。

用 memo[start] 缓存从 start 开始的所有可行句子。

预先统计最大单词长度，减少无效枚举。

复杂度分析：

时间复杂度：O(n * L + 结果总长度)，其中 L 为最大单词长度。

空间复杂度：O(n + 结果总长度)，用于记忆化与结果存储。

class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        Set<String> dict = new HashSet<>(wordDict);
        int maxLen = 0;
        for (String w : wordDict) {
            maxLen = Math.max(maxLen, w.length());
        }

        Map<Integer, List<String>> memo = new HashMap<>();
        return dfs(s, 0, dict, maxLen, memo);
    }

    private List<String> dfs(String s, int start, Set<String> dict, int maxLen,
                             Map<Integer, List<String>> memo) {
        if (memo.containsKey(start)) {
            return memo.get(start);
        }

        List<String> res = new ArrayList<>();
        if (start == s.length()) {
            res.add("");
            return res;
        }

        for (int end = start + 1; end <= s.length() && end - start <= maxLen; end++) {
            String word = s.substring(start, end);
            if (!dict.contains(word)) {
                continue;
            }

            // 递归拼接后续句子
            for (String tail : dfs(s, end, dict, maxLen, memo)) {
                if (tail.isEmpty()) {
                    res.add(word);
                } else {
                    res.add(word + " " + tail);
                }
            }
        }

        memo.put(start, res);
        return res;
    }
}

func wordBreak(s string, wordDict []string) []string {
    dict := make(map[string]struct{})
    maxLen := 0
    for _, w := range wordDict {
        dict[w] = struct{}{}
        if len(w) > maxLen {
            maxLen = len(w)
        }
    }

    memo := make(map[int][]string)

    var dfs func(int) []string
    dfs = func(start int) []string {
        if v, ok := memo[start]; ok {
            return v
        }

        res := make([]string, 0)
        if start == len(s) {
            res = append(res, "")
            return res
        }

        for end := start + 1; end <= len(s) && end-start <= maxLen; end++ {
            word := s[start:end]
            if _, ok := dict[word]; !ok {
                continue
            }

            // 递归拼接后续句子
            for _, tail := range dfs(end) {
                if tail == "" {
                    res = append(res, word)
                } else {
                    res = append(res, word+" "+tail)
                }
            }
        }

        memo[start] = res
        return res
    }

    return dfs(0)
}

相似题目

题目	难度	考察点
139. 单词拆分	中等	动态规划
472. 连接词	困难	DFS、记忆化
79. 单词搜索	中等	DFS
212. 单词搜索 II	困难	Trie、DFS
1268. 搜索推荐系统	中等	字典树

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/95173637