# Very intuitive and concise solution accepted as best in C, well-explained

• Though they are some very instinctive solution just making use of DFS and backtracking but that kind of method will result in bad performance; for acceptable time cost and cleanness of code, I will try to use trie to handle the searching part. There are some problems in this OJ related to this structure too: trie structure and this one also for better searching performance.

Since you now understand what trie actually is then using it to accelerate the searching process will no longer a problem to understand. Right now, probably you might want to ask the tree initialising process can be tedious if the searching range is quite limited; but please think in a big perspective where searching can be used frequently while initialisation is once-for-all thing. ^^ Huh?

Okay let's move on with this problem:

• constructing the trie tree first -> according to the requirements of our algorithm instead of an interchangeable one -> more focused better performance and conciseness;
• start from each point in the matrix to begin the searching process;
• check the children of the root, once it's a word labelled by flag, assemble the collected letter in stack and move to the next cell for further checking until the end of the matrix or a taken cell.

Bang! End of Story!

-space cost will linear to the space of the dictionary words, since we will collect them according to the matrix;
-time cost O(nm4^k) -> n*m is the size of the matrix, k is the longest length of the word in dictionary words considering we will check until the end of the word and each checking will cover 4 directions.

``````#define PLACEHOLDER '#'
#define SIZE 26
struct TrieNode
{
bool isWord;
struct TrieNode **children;
};

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

struct TrieNode* addWords(char** words, int size)
{
struct TrieNode *root = nodeMaker();
struct TrieNode *cur;
for(int i = 0; i < size; i++)
{
cur = root; //always start from the root;
for(int j = 0; words[i][j]; j++)
{
int index = words[i][j]-'a';
if(!(cur->children[index]))
cur->children[index] = nodeMaker();
cur = cur->children[index];
}
cur->isWord = true;
}
return root;
}

void traverse(char** board, int rSize, int cSize, int r, int c, struct TrieNode* root, char* stack, int top, char*** arr, int* returnSize)
{
if(r<0 || c<0 || r==rSize || c==cSize || board[r][c]==PLACEHOLDER) return ; //either out of range or being taken;
char a = board[r][c];
root = root->children[a-'a'];
if(!root) return ;
stack[++top] = a;
if(root->isWord) //hit the word, now collect it;
{
*returnSize += 1;
*arr = (char**)realloc(*arr, sizeof(char*)*(*returnSize));
int len = top+1;
(*arr)[*returnSize-1] = (char*)malloc(sizeof(char)*(len+1));
for(int i = 0; i < len; i++)
(*arr)[*returnSize-1][i] = stack[i];
(*arr)[*returnSize-1][len] = '\0';
root->isWord = false; //already taken, avoid being re-taken;
}
board[r][c] = PLACEHOLDER; //avoid being re-taken by the following four new searchings;
traverse(board, rSize, cSize, r+1, c, root, stack, top, arr, returnSize);
traverse(board, rSize, cSize, r-1, c, root, stack, top, arr, returnSize);
traverse(board, rSize, cSize, r, c+1, root, stack, top, arr, returnSize);
traverse(board, rSize, cSize, r, c-1, root, stack, top, arr, returnSize);
board[r][c] = a; //restore it always after checking each possible path;
}
char** findWords(char** board, int rSize, int cSize, char** words, int wSize, int* returnSize)
{
struct TrieNode *root = addWords(words, wSize);
char** arr = (char**)malloc(sizeof(char*));
char* stack = (char*)malloc(sizeof(char)*SIZE*2);
int top = -1;
for(int r = 0; r < rSize; r++) //start from all the possible cells;
for(int c = 0; c < cSize; c++)
traverse(board, rSize, cSize, r, c, root, stack, top, &arr, returnSize);
return arr;
}
``````

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