LeetCode 212 Word Search II

LeetCode 212

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.

Diffculty
Hard

Similar Problems
[LeetCode 79] Word Search Medium [LeetCode 208] Implement Trie (Prefix Tree) Medium [LeetCode 211] Add and Search Word - Data structure design Medium

Analysis

这道题是 Word Search 的变种，以前只需要判断一个 word，现在提供了一组 words。 如果还按照 DFS 回溯的方法，逐个检查每个 word 是否在 board 里，效率是比较低的。 在这道题最开始更新的几个小时内，用 brute force 是可以通过 OJ 的，就是在之前那题的基础上多加一个 for 循环而已，但是后来出题者其实是想考察字典树的应用，所以加了一个超大的test case，以至于 brute force 无法通过，强制我们必须要用前缀树 Trie 来求解。 简单来说就是，在进行 DFS 遍历时，如果当前形成的单词不在 Trie 里，就没必要继续 DFS 下去了。如果当前字符串在 Trie 里，就说明 board 可以形成这个 word。 我们在这题中只要实现字典树中的 insert 功能就行了，查找单词和前缀就没有必要了，然后 DFS 的思路跟之前那道 Word Search 词语搜索基本相同。

Solutions
class Solution {
public:
    struct TrieNode {
        TrieNode *child[26];
        string str;
        TrieNode() : str("") {
            for (auto &a : child) a = NULL;
        }
    };
    struct Trie {
        TrieNode *root;
        Trie() : root(new TrieNode()) {}
        void insert(string s) {
            TrieNode *p = root;
            for (auto &a : s) {
                int i = a - 'a';
                if (!p->child[i]) p->child[i] = new TrieNode();
                p = p->child[i];
            }
            p->str = s;
        }
    };
    vector<string> findWords(vector<vector<char> >& board, vector<string>& words) {
        vector<string> res;
        if (words.empty() || board.empty() || board[0].empty()) return res;
        vector<vector<bool> > visit(board.size(), vector<bool>(board[0].size(), false));
        Trie T;
        for (auto &a : words) T.insert(a);
        for (int i = 0; i < board.size(); ++i) {
            for (int j = 0; j < board[i].size(); ++j) {
                if (T.root->child[board[i][j] - 'a']) {
                    search(board, T.root->child[board[i][j] - 'a'], i, j, visit, res);
                }
            }
        }
        return res;
    }
    void search(vector<vector<char> > &board, TrieNode *p, int i, int j, vector<vector<bool> > &visit, vector<string> &res) { 
        if (!p->str.empty()) {
            res.push_back(p->str);
            p->str.clear();
        }
        int d[][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        visit[i][j] = true;
        for (auto &a : d) {
            int nx = a[0] + i, ny = a[1] + j;
            if (nx >= 0 && nx < board.size() && ny >= 0 && ny < board[0].size() && !visit[nx][ny] && p->child[board[nx][ny] - 'a']) {
                search(board, p->child[board[nx][ny] - 'a'], nx, ny, visit, res);
            }
        }
        visit[i][j] = false;
    }
};

results matching ""

    No results matching ""