-
Notifications
You must be signed in to change notification settings - Fork 0
/
Word Break
43 lines (36 loc) · 1.27 KB
/
Word Break
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
HashMap<String,Boolean> map= new HashMap<>();
return canConstruct(s, wordDict, map);
}
public boolean canConstruct(String target,List<String> words, HashMap<String,Boolean> map)
{
// if answer already cached, return it
if(map.containsKey(target))
return map.get(target);
// if target string is empty
// it can always be constructed by taking no elements from dictionary
if(target.isEmpty())
return true;
// for all words in the dictionary
for(String word: words)
{
// if the target starts with the given word
if(target.startsWith(word))
{
// and it is possible to construct the rest of the string
// from the words in the dictionary
if(canConstruct(target.substring(word.length()),words, map))
{
// save and return true
map.put(target, true);
return true;
}
}
}
// if it was not possible to construct the target from words from the dictionary
// save and return false to the previous call
map.put(target,false);
return false;
}
}