212 Word Search II

来源：Leetcode

原帖：https://leetcode.com/problems/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.
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"].

代码：

 struct TrieNode {  
   bool isWord;  
   string word;  
   unordered_map<char, TrieNode*> next;  
   TrieNode(bool w = false) : isWord(w) {}  
 };  
   
 class Solution {  
 public:  
   void insert(TrieNode*& root, string s) {  
     if (!root) root = new TrieNode();  
     TrieNode* cur = root;  
     for (int i = 0; i < s.size(); ++i) {  
       if (!cur->next.count(s[i])) {  
         cur->next[s[i]] = new TrieNode();  
       }  
       cur = cur->next[s[i]];  
     }  
     cur->isWord = true;  
     cur->word = s;  
   }  
     
   vector<pair<int,int>> offset = {{0,-1},{-1,0},{0,1},{1,0}};  
   void dfs(vector<vector<char>>& board, vector<vector<bool>>& visited, int i, int j,   
       TrieNode* root, vector<string>& res) {  
     int M = board.size(), N = board[0].size();  
     char c = board[i][j];  
     if (!root->next.count(c)) return;  
     if (root->next[c]->isWord) {  
       res.push_back(root->next[c]->word);  
       root->next[c]->isWord = false;  
     }  
     visited[i][j] = true;  
     for (auto o : offset) {  
       int ii = i + o.first, jj = j + o.second;  
       if (ii >= 0 && ii < M && jj >= 0 && jj < N && !visited[ii][jj]) {  
         dfs(board, visited, ii, jj, root->next[board[i][j]], res);  
       }  
     }  
     visited[i][j] = false;  
   }  
     
   vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {  
     if (words.empty()) return {};  
     TrieNode* root = NULL;  
     for (auto s : words) {  
       insert(root, s);  
     }  
     vector<string> res;  
     int M = board.size(), N = board[0].size();  
     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, visited,i,j,root,res);  
       }  
     }  
     return res;  
   }  
 };