# My AC solution using TrieTree and DFS with 5 ms, but i met a problem.

• all the test case is ok except one.

dict = {"a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"};

s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"

when i add a if condition like:

``````if(s[0] == s[1])
reverse(s.begin(),s.end());
``````

my solution is accepted.

i know why this test case can lead to TimeLimited, but i have no idea to solve it. Help me.

``````struct TrieNode{
char val;
bool isEnd;
TrieNode* next[26] = {NULL};
TrieNode(char x) : val(x), isEnd(false) {}
};

class TrieTree{
private:
TrieNode* root = new TrieNode('a');
public:
void trieInsert(string word){
TrieNode* RootTemp = root;
for(int i = 0; i < word.size(); i++){
if(RootTemp->next[word[i]-'a'] == NULL){
RootTemp->next[word[i]-'a'] = new TrieNode(word[i]);
RootTemp = RootTemp->next[word[i]-'a'];
}
else{
RootTemp = RootTemp->next[word[i]-'a'];
}
}
RootTemp->isEnd = true;
}
bool canBreak(string s){
TrieNode* RootTemp = root;
for(int i = 0; i < s.size(); i++){
if(RootTemp->next[s[i]-'a'] != NULL){
RootTemp = RootTemp->next[s[i]-'a'];
if(RootTemp->isEnd == true){
if(i+1 == s.size()) return true;
if(canBreak(string(s,i+1,s.size()-i-1))) return true;
}
}else return false;
}
return false;
}
};

class Solution {
public:
TrieTree MyTrieTree;
bool wordBreak(string s, unordered_set<string> &dict) {
for(auto& word : dict){
string wordtemp = word;
if(s[0] == s[1])
reverse(wordtemp.begin(),wordtemp.end());
MyTrieTree.trieInsert(wordtemp);
}
if(s[0] == s[1])
reverse(s.begin(),s.end());
return MyTrieTree.canBreak(s);
}
};``````

• Well, I think your algorithm is lucky to pass the OJ because the test case didn't cover like `bbaaaaaaaaaaaaaaa ["a", "aa", "aaa", "aaaa"..."aaaaaaaaaa"]`. After reviewing the member function `canBreak`, may be it uses `Greedy` like method which will easily cause `TLE` for this problem, am I right? Waiting anyone give an idea. Thx.

• Agree. In canBreak(), you used greedy which causes the TLE. I think Trie is a good idea but definitely not necessary in this problem, because it could not improve the time/space time complexity. You can get same complexity through brutal force.

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