Word Break
All break
Brute force is my favourite. However, 2 ^ n seems a huge number.
Something like Jump Game II
That s[0..i] can be break indicates s[i + each d in dict] can be break.
Make a table P, such that, P[i] means if s[0..i] can be break.
dict { leet, code }
Table:
0 1 2 3 4 5 6 7 8 Index
* l e e t c o d e
1 0 0 0 1 0 0 0 1
Calculating P[i]
dict { leet, code }
Table:
0 1 2 3 4 5 6 7 8 Index
* l e e t c o d e
1 0 0 0 1 ? ? ? ?
^
i
here if P[i] wants to be true, either s[0..i] (leetc) or s[4..i] (c) must be in the dict.
So,
P[i] = P[0..j] && s[j..i] in dict, j = 0..i
Source code Read on Github
1 public class Solution {
2 public boolean wordBreak(String s, Set<String> dict) {
3
4 char[] S = s.toCharArray();
5
6 boolean[] P = new boolean[S.length + 1];
7 P[0] = true;
8
9 for(int i = 0; i < S.length; i++){
10
11 for(int j = 0; j <= i; j++){
12 if(P[j] && dict.contains(new String(S, j, i - j + 1))){
13 P[i + 1] = true;
14 continue;
15 }
16 }
17 }
18
19 return P[S.length];
20
21
22 }
23 }