# An intuitive solution may not work out here, using Trie here accepted as best submission in C, well-explained

• If we try to use the intuitive solution to traverse the whole string array to search, the TLE problem will certainly come around; so here we are to take advantage of a new structure Trie which is often used to accelerate the searching process apart from hash and binary search in ordered array.

After getting close to this structure, I assume that you have already know the key to hack it. Needless for further explanation now.

Bang! End of story!

• Space cost O(n)
• Time cost O(kn) -> k should be the length of the word, even all character is dot the worst time complexity will also be limited under 26kn; so that's it.

``````#define SIZE 26
struct WordDictionary
{
bool isWord; //determine whether a word exists in the path;
struct WordDictionary **children;
};

struct WordDictionary* nodeMaker()
{
struct WordDictionary *t = (struct WordDictionary*)malloc(sizeof(struct WordDictionary));
t->isWord = false;
int space = sizeof(struct WordDictionary*)*SIZE;
t->children = (struct WordDictionary**)malloc(space);
memset(t->children, 0, space);
return t;
}
struct WordDictionary* wordDictionaryCreate()
{
return nodeMaker();
}

void addWord(struct WordDictionary* dict, char* word)
{
struct WordDictionary *cur = dict;
for(int i = 0; word[i]; i++)
{
if(!(cur->children[word[i]-'a']))
cur->children[word[i]-'a'] = nodeMaker();
cur = cur->children[word[i]-'a'];
}
cur->isWord = true; //set the flag for the existence of the word in the current path;
}

bool search(struct WordDictionary* root, char* word)
{
struct WordDictionary *cur = root;
for(int i = 0; word[i]; i++)
{
if(!cur) return false; //the path is interrupted;
if(word[i]!='.') //track the path down;
cur = cur->children[word[i]-'a'];
else if(word[i]=='.') //while there is dot, the possible paths can be all;
{
for(int j = 0; j < SIZE; j++) //try every possible path;
if(search(cur->children[j], word+i+1))
return true;
return false; //all possible paths have failed;
}
}
return cur&&cur->isWord; //the last checking;
}

void wordDictionaryFree(struct WordDictionary *dict)
{
free(dict->children);
free(dict);
}
``````

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