Word Break

Word Break

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Solution1

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean wordBreak(String s, List<String> wordDict) {
int length = s.length();
if (length == 0 || s == null || wordDict == null) {
return false;
}

boolean[] dp = new boolean[length + 1];
dp[0] = true;

for (int i = 1; i <= length; i++) {
for (int j = 0; j < i; j++) {
String tmp = s.substring(j, i);
if (dp[j] && wordDict.contains(tmp)) {
dp[i] = true;
break;
}
}
}
return dp[length];
}

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public boolean wordBreak(String s, List<String> wordDict) {
int length = s.length();
if (length == 0 || s == null || wordDict == null) {
return false;
}

Queue<Integer> queue = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
queue.offer(0);
visited.add(0);

while (!queue.isEmpty()) {
int currentIndex = queue.poll();
for (int i = currentIndex + 1; i <= length; i++) {
if (visited.contains(i)) {
continue;
}
if (wordDict.contains(s.substring(currentIndex, i))) {
if (i == length) {
return true;
}
queue.offer(i);
visited.add(i);
}
}
}
return false;
}