Word Break (Trie)
Given a string A and a dictionary of n words B, find out if A can be segmented into a space-separated sequence of dictionary words.
- Time : O(n^2)
Space : O(b)
dnc solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
unordered_set<string> us;
unordered_map<string, bool> dp;
bool dnc(string A) {
if(us.count(A)) return true;
if(dp.count(A)) return dp[A];
dp[A] = false;
for(int i = 1; i < A.length(); i++) {
if(dnc(A.substr(0, i)) && dnc(A.substr(i)))
return dp[A] = true;
}
return dp[A];
}
public:
int wordBreak(string A, vector<string> &B) {
us = unordered_set<string>(begin(B), end(B));
return dnc(A);
}
};
|
- Time : O(2^n)
Space : O(b)
trie solution
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
| struct Trie {
unordered_map<char, Trie*> nxt;
bool eof = false;
void insert(string& s, int p = 0) {
if(p == s.length()) eof = true;
else {
if(!nxt.count(s[p])) nxt[s[p]] = new Trie();
nxt[s[p]]->insert(s, p + 1);
}
}
};
class Solution {
Trie* trie;
vector<bool> vis;
bool helper(string& A, int pos) {
if(pos == A.length()) return true;
if(vis[pos]) return false;
vis[pos] = true;
Trie* t = trie;
for(; pos < A.length(); pos++) {
if(t->eof && helper(A,pos)) return true;
if(!t->nxt.count(A[pos])) return false;
t = t->nxt[A[pos]];
}
return t->eof;
}
public:
int wordBreak(string A, vector<string> &B) {
vis = vector<bool>(A.length());
trie = new Trie();
for(auto& b : B)
if(b.length() <= A.length())
trie->insert(b);
return helper(A, 0);
}
};
|
