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.

Example:

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

Output: ["eat","oath"]

Note:

All inputs are consist of lowercase letters a-z.
The values of words are distinct.

class Solution {
private:
    int row, col;
    vector<vector<char>> board_;
    vector<vector<bool>> occupancy;
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        vector<string> ret;
        unordered_map<char, vector<pair<int,int>>> position;
        
        row = board.size();
        if (row == 0) return ret;
        col = board[0].size();
        
        board_ = board;
        occupancy = vector<vector<bool>>(row, vector<bool>(col, false));
        
        for (int r=0; r<row; ++r){
            for (int c=0; c<col; ++c) {
                position[board[r][c]].push_back(make_pair(r, c));
            }
        }
        
        bool succ;
        for (const auto word : words) {
            for (const auto& [r,c] : position[word[0]]) {
                occupancy[r][c] = true;
                succ = dfs(r, c, word, 1);
                occupancy[r][c] = false;
                if (succ) {
                    ret.push_back(word);
                    break;
                }
            }
        }
            
        return ret;
    }
    
    bool dfs(const int& r, const int& c, const string& word, const int& index) {
        if (index == word.size()) return true;
        bool succ;
        
        if (r+1<row and board_[r+1][c] == word[index] and occupancy[r+1][c] == false) {
            occupancy[r+1][c] = true;
            succ = dfs(r+1, c, word, index+1);
            occupancy[r+1][c] = false;
            if (succ) return true;
        }
        
        if (c-1>-1 and board_[r][c-1] == word[index] and occupancy[r][c-1] == false) {
            occupancy[r][c-1] = true;
            succ = dfs(r, c-1, word, index+1);
            occupancy[r][c-1] = false;
            if (succ) return true;
        }
        
        if (r-1>-1 and board_[r-1][c] == word[index] and occupancy[r-1][c] == false) {
            occupancy[r-1][c] = true;
            succ = dfs(r-1, c, word, index+1);
            occupancy[r-1][c] = false;
            if (succ) return true;
        }
        
        if (c+1<col and board_[r][c+1] == word[index] and occupancy[r][c+1] == false) {
            occupancy[r][c+1] = true;
            succ = dfs(r, c+1, word, index+1);
            occupancy[r][c+1] = false;
            if (succ) return true;
        }
        
        return false;
    }
};

我的解法使用DFS，总体没什么问题，但是35/36case会超时：
https://leetcode.com/submissions/detail/410900627/testcase/

其中可以改进的细节：

• dfs的判断全部放到loop里面，而不是一部分放在外面
• 上一条基础上，可以把dfs里面的4个大{}都简化，先搜索再说
• 不用occupancy matrix，直接修改board就可以了，搜索过的赋值“#”

解决超时的办法： trie tree + dfs

只搜索trie tree而不是遍历words

https://zxi.mytechroad.com/blog/searching/leetcode-212-word-search-ii/

复现：

class Solution {
private:
    class TrieNode {
        public:
            TrieNode () {
            }
            shared_ptr<string> word = nullptr;
            vector<shared_ptr<TrieNode>> next = vector<shared_ptr<TrieNode>>(26, nullptr);
    };
    
    vector<string> ret;
    int row, col;
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        // building Trie Tree
        shared_ptr<TrieNode> root(new TrieNode());
        for (const auto& word : words) {
            shared_ptr<TrieNode> curr = root;
            for (const auto& c : word) {
                int index = c - 'a';
                if (!curr->next[index]) {
                    curr->next[index] = make_shared<TrieNode>();
                }
                curr = curr->next[index];
            }
            curr->word = make_shared<string>(word);
        }
        
        row = board.size();
        col = board[0].size();
        for (int r=0; r<row; ++r) {
            for (int c=0; c<col; ++c) {
                dfs(root, board, r, c);
            }
        }
        
        return ret;
    }
    
    void dfs(shared_ptr<TrieNode> node, vector<vector<char>>& board, const int& r, const int& c) {
        if (r<0 or r>=row or c<0 or c>=col) return;
        int cache = board[r][c]-'a';
        if (cache=='#'-'a' or node->next[cache]==nullptr) return;
        
        if (node->next[cache]->word != nullptr) {
            ret.push_back(*node->next[cache]->word);
            node->next[cache]->word = nullptr;
        }
        
        board[r][c] = '#';
        
        dfs(node->next[cache], board, r+1, c);
        dfs(node->next[cache], board, r-1, c);
        dfs(node->next[cache], board, r, c+1);
        dfs(node->next[cache], board, r, c-1);
        
        board[r][c] = cache+'a';
    }
};

注意事项：

• TrieTree word需要在node->next[cache]->word 而不是node->word

Runtime: 156 ms, faster than 51.36% of C++ online submissions for Word Search II.
Memory Usage: 53.2 MB, less than 5.12% of C++ online submissions for Word Search II.