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


  • 1

    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;
    }
    

Log in to reply
 

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