212. Word Search II ----H ~~~~~~~~

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:

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

A:
就是用Trie了， 自己建Trie要麻烦些罢了。
然后用DFS即可。

class Solution {
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        vector<string> res;
        int m = board.size();
        if(m== 0)
            return res;
        int n = board[0].size();
        Node* root = buildTrie(words);
        unordered_set<string> resSet;// to avoid duplicates
        vector<vector<bool>> visited(m,vector<bool>(n, false));
        for(int i =0;i<m;i++){
            for(int j = 0; j<n;j++){
                dfs(board, i,j,root->kids[board[i][j]], resSet, visited);
            }
        }
        res.assign(resSet.begin(),resSet.end());
        return res;
    }
private:
    struct Node{
        unordered_map<char,Node*> kids; // cannot declare here. (26,nullptr);
        bool isLeaf;
        char cur;
        string curWord;
        Node(char ch):cur(ch),isLeaf(false),curWord(""){}
    };
    Node* buildTrie(vector<string> &words){
        Node* root = new Node(' ');
        for(auto word: words){
            auto pre = root; // auto & pre = root is WRONG. DO NOT reference a pointer
            for(auto ch : word){
                if(not pre->kids[ch]){
                    pre->kids[ch] = new Node(ch);
                }
                pre = pre->kids[ch];
            }
            pre->isLeaf = true;
            pre->curWord = word;
        }
        return root;
    }
    void dfs(vector<vector<char>>& board, int i, int j, const Node* root, unordered_set<string>& resSet, vector<vector<bool>>& visited){
        int m = board.size();
        int n = board[0].size();
        if(i<0 || i>=m || j<0 || j>=n || visited[i][j] || not root){
            return;
        }
        if(root->cur == board[i][j]){
            visited[i][j] = true;
            if(root->isLeaf){
                resSet.insert(root->curWord);
            }
            vector<vector<int>> Diff{ {-1,0},{1,0},{0,-1},{0,1}};
            for(auto& d : Diff){
                for(auto kid : root->kids){
                    dfs(board, i+d[0], j + d[1], kid.second, resSet,visited);
                }
            }
            visited[i][j] = false;
        }
    }
};

Mistakes:
1:  even isLeaf==true, 也需要继续找下去。  例如 words = {"the", "they" "their"}

2: 没有处理一个word被多次找到的情况。i.e.   word节点可能被多次找到，

例如输入是    {{'a'}} , {"a"}的时候。
   这样，我们就需要 每次见dfs下一层， 进去之后再检查 flag  matrix是否  valid
 但是，这样又会出现 一个位置 多次计算的问题。
 因此还是要  每次进入之前检测。
其实还是对自己的这个Trie的定义的理解问题。  代码里，我们是先到一个TrieNode之后，再检测该位置是否match，然后再试探着dfs

3： 
这个题目的关键点（for me）  就是 考虑到root的定义， 我们初始dfs的 时候，就要进入root的下一个TrieNode.

dfs(board, i,j,root->kids[board[i][j]], resSet, visited);