Concise C++ Trie + backtracking solution, 65 ms


  • 0
    Y
    class TrieNode {
    public:
        TrieNode *child[26];
        bool isWord;
        TrieNode() {
            for (int i = 0; i < 26; i++) child[i] = NULL;
            isWord = false;
        }
    };
    
    class Solution {
    public:
        vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
            vector<string> ans;
            int m = board.size();
            if (m == 0) return ans;
            int n = board[0].size();
            if (n == 0) return ans;
            
            if (words.empty()) return ans;
            
            TrieNode *root = new TrieNode;
            for (int i = 0; i < words.size(); i++) addWord(root, words[i]);
            
            vector<vector<bool>> mark(m, vector<bool>(n, false));
            string cur;
            
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    helper(ans, board, mark, cur, root, i, j, m, n);
                }
            }
            
            return ans;
        }
        
        void addWord(TrieNode *root, string &word) {
            TrieNode *p = root;
            for (int i = 0; i < word.size(); i++) {
                int pos = word[i] - 'a';
                if (!p->child[pos]) p->child[pos] = new TrieNode;
                p = p->child[pos];
            }
            p->isWord = true;
        }
        
        void helper(vector<string> &ans, vector<vector<char>> &board, vector<vector<bool>> &mark, string &cur, TrieNode *p, int x, int y, int m, int n) {
            if (x < 0 || x >= m || y < 0 || y >= n || mark[x][y]) return;
            
            int pos = board[x][y] - 'a';
            if (!p->child[pos]) return;
            else p = p->child[pos];
            
            mark[x][y] = true;
            cur.push_back(board[x][y]);
            
            if (p->isWord) {
                ans.push_back(cur);
                p->isWord = false;  // avoid duplicates
            }
            
            helper(ans, board, mark, cur, p, x - 1, y, m, n);
            helper(ans, board, mark, cur, p, x + 1, y, m, n);
            helper(ans, board, mark, cur, p, x, y - 1, m, n);
            helper(ans, board, mark, cur, p, x, y + 1, m, n);
            
            cur.pop_back();
            mark[x][y] = false;
        }
    };
    

Log in to reply
 

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