212. Word Search II (Hard)

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.

For example,

Given words = ["oath","pea","eat","rain"] and board =

[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

Return ["eat","oath"].

Note:

You may assume that all inputs are consist of lowercase letters a-z.

Hint:

You would need to optimize your backtracking to pass the larger test. Could you stop backtracking earlier?

If the current candidate does not exist in all words' prefix, you could stop backtracking immediately. What kind of data structure could answer such query efficiently? Does a hash table work? Why or why not? How about a Trie? If you would like to learn how to implement a basic trie, please work on this problem: Implement Trie (Prefix Tree) first.

Solution: Trie

这道题是在之前那道Word Search 词语搜索的基础上做了些拓展，之前是给一个单词让判断是否存在，现在是给了一堆单词，让返回所有存在的单词，在这道题最开始更新的几个小时内，用brute force是可以通过OJ的，就是在之前那题的基础上多加一个for循环而已，但是后来出题者其实是想考察字典树的应用，所以加了一个超大的test case，以至于brute force无法通过，强制我们必须要用字典树来求解。LeetCode中有关字典树的题还有 Implement Trie (Prefix Tree) 实现字典树(前缀树)和Add and Search Word - Data structure design 添加和查找单词-数据结构设计，那么我们在这题中只要实现字典树中的insert功能就行了，查找单词和前缀就没有必要了，然后DFS的思路跟之前那道Word Search 词语搜索基本相同，请参见代码如下：

version 1: 59ms

class Solution {
public:
    int m, n;
    struct TrieNode {
        vector<TrieNode*> child;
        string word;
        TrieNode(): child(vector<TrieNode*>(26, NULL)) {}
    };

    TrieNode* buildTrie(vector<string>& words) {
        TrieNode* root = new TrieNode();
        for (string& word: words) {
            TrieNode* cur = root;
            for (char& a: word) {
                int i = a-'a';
                if (!cur->child[i]) cur->child[i] = new TrieNode();
                cur = cur->child[i];
            }
            cur->word = word;
        }
        return root;
    }

    void dfs(vector<vector<char>>& board, int i, int j, TrieNode* p, vector<string>& res) {
        if (i < 0 || i >= m || j < 0 || j >= n) return;
        char c = board[i][j];
        if (c == '#' || !p->child[c-'a']) return;
        p = p->child[c-'a'];
        if (p->word != "") {
            res.push_back(p->word);
            p->word = ""; // prevent duplicate
        }
        board[i][j] = '#';
        dfs(board, i-1, j, p, res);
        dfs(board, i+1, j, p, res);
        dfs(board, i, j-1, p, res);
        dfs(board, i, j+1, p, res);
        board[i][j] = c;
    }

    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        vector<string> res;
        m = board.size(); n = board[0].size();
        if (words.empty() || m == 0 || n == 0) return res;
        TrieNode* root = buildTrie(words);

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                dfs(board, i, j, root, res);
            }
        }
        return res;
    }
};

version 2: 55ms

class Solution {
    struct TreeNode {
        bool isWord;
        vector<TreeNode*> children;
        TreeNode(): isWord(false), children(26,NULL) {}
    };

    void addWord(string& word) {
        TreeNode* cur = root;
        for (auto& c: word) {
            if (!cur->children[c-'a']) cur->children[c-'a'] = new TreeNode();
            cur = cur->children[c-'a'];
        }
        cur->isWord = true;
    }

    void dfs(vector<vector<char>>& board, int row, int col, TreeNode* p, string path, vector<string>& res) {
        if (p->isWord) {
            p->isWord = false;
            res.push_back(path);
        }

        for (int i = 0; i < 4; ++i) {
            int x = row+dir[i], y = col+dir[i+1];
            if (x >= 0 && x < board.size() && y >= 0 && y < board[0].size() && board[x][y] != '#') {
                char c = board[x][y];
                if (p->children[c-'a']) {
                    board[x][y] = '#';
                    dfs(board, x, y, p->children[c-'a'], path+c, res);
                    board[x][y] = c;
                }
            }
        }
    }
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        root = new TreeNode();
        for (auto& w: words) addWord(w);
        vector<string> res;
        for (int i = 0; i < board.size(); ++i) {
            for (int j = 0; j < board[0].size(); ++j) {
                char c = board[i][j];
                if (root->children[c-'a']) {
                    board[i][j] = '#';
                    dfs(board, i, j, root->children[c-'a'], string(1,c), res);
                    board[i][j] = c;
                }
            }
        }
        return res;
    }

private:
    TreeNode* root;
    vector<int> dir = {0,-1,0,1,0};
};