LeetCode 139. 单词拆分

题目描述

✅ 139. 单词拆分

image-20250420015616151

image-20250420015630735

思路分析

完全背包排列问题

dp[i] 表示 s[0:i] 是否可以被拆分成字典单词的组合

image-20250508023542221

参考代码



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22



func wordBreak(s string, wordDict []string) bool {
	dict := map[string]bool{}
	for _, word := range wordDict {
		dict[word] = true
	}

	// dp[i] 表示 s[:i] 是否可以被拆分
	n := len(s)
	dp := make([]bool, n+1)
	dp[0] = true // 空字符串可以被拆分

	for i := 1; i <= n; i++ {
		for j := 0; j < i; j++ {
			if dp[j] && dict[s[j:i]] {
				dp[i] = true
				break // 提前剪枝
			}
		}
	}

	return dp[n]
}
  • 时间复杂度：O(n²)，其中 n 为字符串长度，嵌套循环 i 和 j。
  • 空间复杂度：O(n + m)，n 为 dp 数组长度，m 为字典哈希表大小。

➡️ 点击查看 Java 题解



1



write your code here
本文作者:
本文链接: https://hgnulb.github.io/blog/2025/14966021
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！