# DFS+Trie solution MLE

• My submission shows that 43 test cases passed but got a MLE. Does anyone knows how to fix it?

``````struct TrieNode
{
bool flag;
TrieNode *childs[26];
TrieNode *parent;
TrieNode() :parent(NULL), flag(false) {
for (int i = 0; i < 26; i++)
childs[i] = NULL;
}
};
void insertWord(TrieNode *p, char* word)
{
if ((*word)=='\0')
{
p->flag = true;
return;
}
int index = word[0] - 'a';
if (p->childs[index] == NULL)
p->childs[index] = new TrieNode();
if (p->childs[index]->parent == NULL)
p->childs[index]->parent = p;
insertWord(p->childs[index],word+1);
}
vector<int> getCanSplitPoints(TrieNode *p, char *s)
{
int index;
vector<int> result;
int i = 0;
while ((*s)!='\0')
{
index = (*s) - 'a';
if (p->childs[index] != NULL)
{
if (p->childs[index]->flag) result.push_back(i);
p = p->childs[index];
i++;
s++;
}
else break;
}
return result;
}
bool search(TrieNode *p, char *s, int &count,set<string> &resultSet)
{
if ((*s)=='\0') return true;
vector<int> points = getCanSplitPoints(p, s);
bool tmpflag;
if (points.size())
{
for (int i = 0; i < points.size(); i++)
{
count++;
string tmp = string(s + points[i] + 1);
if (resultSet.find(string(s + points[i] + 1)) != resultSet.end())
return true;
if (search(p,s+points[i] + 1, count,resultSet) && count>1)
return true;
count--;
}
return false;
}
return false;
}
class Solution {
public:

TrieNode *root = new TrieNode();
char* c = new char[2000];
for (int i = 0; i < words.size(); i++)
{
strcpy(c, words[i].c_str());
insertWord(root, c);
}
vector<string> result;
set<string> s;
int count;
for (int i = 0; i < words.size(); i++)
{
count = 0;
strcpy(c, words[i].c_str());
if (search(root, c, count,s) && words[i] != "")
{
result.push_back(words[i]);
s.insert(words[i]);
}
}
return result;
}
};``````

• It's not a good idea to use raw pointer in c++,
and I think you can improve your Trie Tree implement.

• You need to release memory and do other optimizations. I have opened another topic. You are welcomed to check if you are still interested.

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