# Trie + recursion + memorization

• The basic idea:

• use Trie to store the dictionary.
• then, use recursion to check all possible word break.
• use memorization to avoid duplicate computation.

Here is the code:

``````class TrieNode {
bool isWord;
TrieNode * child[26];
public:
TrieNode() {
isWord = false;
for (int i = 0; i < 26; i++)
child[i] = NULL;
}
bool isEnd() {
return isWord;
}
void setEnd() {
isWord = true;
}
TrieNode * getNode(char ch) {
return child[ch - 'a'];
}
void setNode(char ch) {
child[ch - 'a'] = new TrieNode();
}
};

class Solution {
TrieNode * root;
vector<int> mem;
int n;
TrieNode * pt = root;
for (auto i : word) {
if (!pt->getNode(i))
pt->setNode(i);
pt = pt->getNode(i);
}
pt->setEnd();
}

//this function will return positions of all words align with s[pos...]
vector<int> longestPrefix(const string & s, int pos) {
TrieNode * pt = root;
vector<int> res;
while (pos < n) {
if (!pt->getNode(s[pos]))
return res;
pt = pt->getNode(s[pos]);
if (pt->isEnd())//find one word, store its index and keep digging
res.push_back(pos);
pos++;
}
return res;
}
public:
bool wordBreak(string s, unordered_set<string>& wordDict) {
root = new TrieNode();
for (auto i : wordDict)
n = s.length();
mem = vector<int> (n, 0);
return wordBreak(s, 0);
}
bool wordBreak(const string & s, int pos) {
if (mem[pos])
return mem[pos] == 1 ? true : false;
vector<int> res = longestPrefix(s, pos);
if (!res.empty()) {
for (auto i : res)
if (i == n - 1 || wordBreak(s, i + 1))
return mem[pos] = 1;
}
mem[pos] = -1;
return false;
}
};
``````

• When I use dfs + memoization ,It still pass all the test.But when I use trie + dfs, I got the TLE error.
Do search in the trie really faster than the search in unordered_set?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.