44 ms C++ solution with comments


  • 1
    V

    The main idea is to insert all search words into a trie initially. When searching through the board, only check letters if a path to that letter exists within the trie. This guarantees that it will be a prefix of a word in the list. Recursively check the paths keeping track of a pointer position to the corresponding prefix in the trie.

    class TrieNode {
    public:
        // Trie node with char value and two boolean values, 
        // one for leaf status and one for found status
        char val;
        bool leaf;
        bool found;
        TrieNode *next[26]; //ptrs to nodes with letters a-z
        
        TrieNode() : leaf(false), found(false)
        {
            memset(next, 0, sizeof(TrieNode*)*26);
        }
        TrieNode(char c) : val(c), leaf(false), found(false)
        {
            memset(next, 0, sizeof(TrieNode*)*26);
        }
    };
    
    class Trie {
    public:
        Trie() {
            root = new TrieNode();
        }
    
        // Inserts a word into the trie.
        void insert(string word) {
            TrieNode *cur = root;
            
            for(int i=0; i<word.size(); ++i) {
                char next = word[i];
                if(cur->next[next-'a'])
                    cur = cur->next[next-'a'];
                else {
                    TrieNode *node = new TrieNode(next);
                    cur->next[next-'a'] = node;
                    cur = cur->next[next-'a'];
                }
            }
            
            cur->leaf = true;
        }
    
        //returns pointer to root node
        TrieNode *GetRoot() {
            return root;
        }
    private:
        TrieNode* root;
    };
    
    class Solution {
    public:
        void find(const vector<vector<char>> &board, bool **path, string &curWord, TrieNode *node,
                    vector<string> &res, const int i, const int j, const int m, const int n) {
            
            //if leaf node then we have found a word, so mark it as found and push back into res
            if(node->leaf && !node->found) {
                res.push_back(curWord);
                node->found = true;
            }
                
            char next;
            path[i][j] = true;     //mark path so we don't trace over letters that have already been used
                
            //search up, down, left, and right if there are entries in the trie corresponding to those letters
            if(i-1 >= 0) {
                next = board[i-1][j];
                if(node->next[next-'a'] && !path[i-1][j]) {
                    curWord.push_back(next);
                    find(board, path, curWord, node->next[next-'a'], res, i-1, j, m, n);
                    curWord.pop_back();
                }
            }
            
            if(i+1 < m) {
                next = board[i+1][j];
                if(node->next[next-'a'] && !path[i+1][j]) {
                    curWord.push_back(next);
                    find(board, path, curWord, node->next[next-'a'], res, i+1, j, m, n);
                    curWord.pop_back();
                }
            }
            
            if(j-1 >= 0) {
                next = board[i][j-1];
                if(node->next[next-'a'] && !path[i][j-1]) {
                    curWord.push_back(next);
                    find(board, path, curWord, node->next[next-'a'], res, i, j-1, m, n);
                    curWord.pop_back();
                }
            }
            
            if(j+1 < n) {
                next = board[i][j+1];
                if(node->next[next-'a'] && !path[i][j+1]) {
                    curWord.push_back(next);
                    find(board, path, curWord, node->next[next-'a'], res, i, j+1, m, n);
                    curWord.pop_back();
                }
            }
            
            path[i][j] = false;
        }
    
        vector<string> findWords(vector<vector<char>>& board, vector<string> &words) {
            
            vector<string> res;
            int m = board.size();
            if(m == 0)
                return res;
            int n = board[0].size();
            int wsize = words.size();
            if(wsize == 0)
                return res;
            
            bool **path = new bool*[m];
            for(int i=0; i<m; ++i) {
                path[i] = new bool[n];
                memset(path[i], false, sizeof(bool)*n);
            }
            
            //insert all words into Trie
            Trie TR;
            for(int i=0; i<wsize; ++i)
                TR.insert(words[i]);
            
            string curWord;
            TrieNode *TriePtr = TR.GetRoot();
            for(int i=0; i<m; ++i)
                for(int j=0; j<n; ++j)
                    if(TriePtr->next[board[i][j]-'a']) {
                        curWord.push_back(board[i][j]);     //push initial letter into current word
                        find(board, path, curWord, TriePtr->next[board[i][j]-'a'], res, i, j, m, n);
                        curWord.pop_back();                 //pop afterwards
                    }
                    
            return res;
        }
    };

Log in to reply
 

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