leetcode212-word-search-II

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example:

Input: 
words = ["oath","pea","eat","rain"] and board =
[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

Output: ["eat","oath"]

• idea:
  trie + dfs

• code:

  • trie:

    class TrieNode {
    public:
        bool is_end;
        vector<TrieNode*> children;
        TrieNode() {
            is_end = false;
            children = vector<TrieNode*>(26, NULL);
        }
    };
    
    class Trie {
    public:
        TrieNode* getRoot() {
            return root;
        }
    
        Trie(vector<string>& words) {
            root = new TrieNode;
            for (int i = 0; i < words.size(); i++) {
                addWord(words[i]);
            }
        }
    
        void addWord(const string& word) {
            TrieNode* cur = root;
            for (int i = 0; i < word.size(); i++) {
                int index = word[i] - 'a';
                if (cur->children[index] == NULL) {
                    cur->children[index] = new TrieNode();
                }
                cur = cur->children[index];
            }
            cur->is_end = true;
        }
        
    private:
        TrieNode* root;
    };

  • body

    class Solution {
    public:
        vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
            Trie* trie = new Trie(words);
            TrieNode* root = trie->getRoot();
            set<string> result_set;
            row = board.size();
            col = board[0].size();
            for (int r = 0; r < row; r++) {
                for (int c = 0; c < col; c++) {
                    findWords(board, r, c, root, "", result_set);
                }
            }
            
            vector<string> result;
            for (auto candidate : result_set) {
                result.push_back(candidate);
            }
            return result;
        }
        
    private:
        int row;
        int col;
        void findWords(vector<vector<char>>& board, int r, int c, TrieNode* root, string word, set<string>& result) {
            if (r < 0 || r == row || c < 0 || c == col || board[r][c] == ' ') {
                return;
            }
            
            if (root->children[board[r][c] - 'a'] != NULL) {
                word = word + board[r][c];
                root = root->children[board[r][c] - 'a'];
                if (root->is_end) {
                    result.insert(word);
                }
                
                char backtrace = board[r][c];
                board[r][c] = ' ';
                findWords(board, r + 1, c, root, word, result);
                findWords(board, r - 1, c, root, word, result);
                findWords(board, r, c + 1, root, word, result);
                findWords(board, r, c - 1, root, word, result);
                board[r][c] = backtrace;
            }
        }
    };