# Question

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

# Example

Gieve s = lintcode,
dict = ["de", "ding", "co", "code", "lint"].

A solution is ["lint code", "lint co de"].

RunTime : 902ms

``````class Solution {
public:
/*
* @param s: A string
* @param dict: A dictionary of words dict
* @return: A boolean
*/
vector<string> wordBreak(string &s, unordered_set<string> &dict) {
result.clear();
if (s.length() <= 0)
return result;
bool found = true;
for (auto c : s) {
bool in = false;
for (auto d : dict) {
if (in)
break;
for (auto e : d) {
if (e == c) {
in = true;
break;
}
}
}
if (!in) {
found = false;
break;
}
}
if (!found)
return result;
Trie trie;
for (auto d : dict)
trie.insert(d);
string bw;
wordBreakHelp(s, trie, 0, bw);
return result;
}
private:
vector<string> result;
struct TrieNode {
TrieNode() {
for (int i = 0; i < 26; i++) {
next[i] = 0;
}
s = 0;
}
int s;
TrieNode* next[26];
};
class Trie {
public:
Trie() {
root = new TrieNode();
}
inline void deleteHelper(TrieNode* root) {
if (root) {
for (int i = 0; i < 26; i++) {
deleteHelper(root->next[i]);
}
delete root;
}
}
~Trie() {
deleteHelper(root);
root = 0;
}
void insert(string& s) {
TrieNode* iter = root;
for (auto c : s) {
if (iter->next[c - 'a'] == 0)
iter->next[c - 'a'] = new TrieNode();
iter = iter->next[c - 'a'];
}
iter->s = s.length();
}
unordered_set<int> search(string& s, int pos) {
TrieNode* iter = root;
unordered_set<int> words;
for (size_t i = pos; i < s.length(); i++) {
char c = s[i];
if (iter->next[c - 'a'] == 0)
break;
if (iter->s > 0) {
words.insert(iter->s);
}
iter = iter->next[c - 'a'];
}
if (iter->s > 0) {
words.insert(iter->s);
}
return words;
}
private:
TrieNode* root;
};
inline void wordBreakHelp(string& s, Trie& trie, int pos, string& bw) {
unordered_set<int> words = trie.search(s, pos);
if (words.size() > 0) {
for (auto word : words) {
string bwd = bw;
if (bwd.empty())
bwd = s.substr(pos, word);
else {
bwd.append(" ");
bwd.append(s.substr(pos, word));
}
if ((pos + word) == s.length()) {
result.push_back(bwd);
}
else {
wordBreakHelp(s, trie, pos + word, bwd);
}
}
}
}
};
``````