C++ 50ms 33 lines clean Trie solution with comments


  • 0
    class TrieNode {
    public:
        bool isWord = false;
        TrieNode* children[26];
        TrieNode() { memset(children, NULL, sizeof(children)); }
    };
    
    class Solution {
    private:
        unordered_set<string> s;                                        // hash set to record unique word
        TrieNode* root = new TrieNode();                                // root node for words trie
        int m, n, dirs[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};      // up, right, down, left
        string path = "";
        
        void addWord(string& word, int start, TrieNode* cur) {          // helper function to add word in trie
            if (start == word.length()) { cur->isWord = true; return; }
            int idx = word[start] - 'a';
            if (!cur->children[idx]) { cur->children[idx] = new TrieNode(); }
            addWord(word, start + 1, cur->children[idx]);
        }
        
        void search(vector<vector<char>>& board, int r, int c, TrieNode* cur) {                 // recursively search board
            if (r < 0 || r == m || c < 0 || c == n || !cur->children[board[r][c] - 'a'] || board[r][c] == ' ') { return; }
            
            path.push_back(board[r][c]);                                                        // record current char
            if ((cur = cur->children[board[r][c] - 'a'])->isWord) { s.insert(path); }           // record any found word
            board[r][c] = ' ';                                                                  // mark it as visited
            for (auto dir : dirs) { search(board, r + dir[0], c + dir[1], cur); }               // search neighbours
            board[r][c] = path.back();                                                          // clear marker
            path.pop_back();                                                                    // recover path
        }
        
    public:
        vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
            vector<string> ans;
            if ( (m = board.size()) == 0 || (n = board[0].size()) == 0) { return ans; }
            
            for (string word : words) { addWord(word, 0, root); }                       // build trie for words
            
            for (int r = 0; r < m; r++) {
                for (int c = 0; c < n; c++) { search(board, r, c, root); }              // recursively search board
            }
            
            for (auto it = s.begin(); it != s.end(); it++) { ans.push_back(*it); }      // generate answer
            return ans;
        }
    };
    

Log in to reply
 

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