Leetcode
Dynamic Programming
139 Word Break

139. Word Break

1. Question

Given a non-empty strings and a dictionary wordDict containing a list of non-empty words, determine if scan be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.
For example, given s="leetcode", dict=["leet", "code"].
Return true because"leetcode"can be segmented as"leet code".

2. Implementation

(1) DFS + Memoinzation
1
class Solution {
2
public boolean wordBreak(String s, List<String> wordDict) {
3
Map<Integer, Boolean> map = new HashMap<>();
4
Set<String> dict = new HashSet<>(wordDict);
5
6
return isBreakable(0, s, dict, map);
7
}
8
9
public boolean isBreakable(int start, String s, Set<String> dict, Map<Integer, Boolean> map) {
10
if (start == s.length()) {
11
return true;
12
}
13
14
if (map.containsKey(start)) {
15
return map.get(start);
16
}
17
18
boolean breakable = false;
19
20
for (int end = start + 1; end <= s.length(); end++) {
21
if (dict.contains(s.substring(start, end)) && isBreakable(end, s, dict, map)) {
22
breakable = true;
23
}
24
}
25
26
map.put(start, breakable);
27
return breakable;
28
}
29
}
Copied!
(2) DP
1
class Solution {
2
public boolean wordBreak(String s, List<String> wordDict) {
3
Set<String> dict = new HashSet<>(wordDict);
4
int n = s.length();
5
boolean[] dp = new boolean[n + 1];
6
dp[0] = true;
7
8
for (int i = 1; i <= n; i++) {
9
for (int j = 0; j < i; j++) {
10
if (dp[j] && dict.contains(s.substring(j, i))) {
11
dp[i] = true;
12
break;
13
}
14
}
15
}
16
return dp[n];
17
}
18
}
Copied!

3. Time & Space Complexity

DFS + Memoinzation: 时间复杂度O(n^2), 空间复杂度O(n)
DP: 时间复杂度O(n^2), 空间复杂度O(n)