给定一个二维网格 board 和一个字典中的单词列表 words，找出所有同时在二维网格和字典中出现的单词。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

  1. 输入: 
  2. words = ["oath","pea","eat","rain"] and board =
  3. [
  4.   ['o','a','a','n'],
  5.   ['e','t','a','e'],
  6.   ['i','h','k','r'],
  7.   ['i','f','l','v']
  8. ]
  10. 输出: ["eat","oath"]

Trie

  1. class Trie {
  2.     struct TrieNode {
  3.     bool end;
  4.     string str;
  5.     unordered_map<char, TrieNode *> child;
  6.     TrieNode(): end(false), str("") {};
  7. };
  8. public:
  9.     Trie() {
  10.         root = new TrieNode();
  11.     }
  12.     void insert(string word) {
  13.         TrieNode *cur = root;
  14.         for (int i = 0; i < word.size(); i++) {
  15.             if (cur->child.count(word[i]) == 0) {
  16.                 cur->child[word[i]] = new TrieNode();
  17.             }
  18.             cur = cur->child[word[i]];
  19.         }
  20.         cur->str = word;             //下一个节点存单词， 当前节点不存。
  21.         cur->end = true;
  22.     }
  24.     void search(vector<string>& res, vector<vector<char>>& board) {
  25.         for (int i = 0; i < board.size(); i++) {
  26.             for (int j = 0; j < board[i].size(); j++) {
  27.                 help(res, board, root, i, j);
  28.             }
  29.         }
  30.     }
  31.     void help(vector<string>& res, vector<vector<char>>& board, TrieNode *p, int x, int y) {
  32.         if (p->end) {      //因为trie树把单词存入下一个节点，所以这里进来就判断是不是单词结尾，走到该处，说明有一个完整的单词
  33.             res.push_back(p->str);
  34.             p->end = false; //防止重复添加
  35.             return;
  36.         }
  37.         if (x < 0 || x == board.size() || y < 0 || y == board[x].size()) return; //判断边界
  38.         if (p->child.find(board[x][y]) == p->child.end()) return; //当前节点的map中找不到board中四通图的字符则返回
  39.         //下面是找到了字符
  40.         p = p->child[board[x][y]]; //找下一个节点，下一个节点end为true的话，说明找到了完整的单词
  41.         char cur = board[x][y];
  42.         board[x][y] = '#';
  43.         help(res, board, p, x + 1, y); //不能先算减一
  44.         help(res, board, p, x - 1, y);
  45.         help(res, board, p, x, y + 1); //同上
  46.         help(res, board, p, x, y - 1);
  47.         board[x][y] = cur;
  48.     }
  49. private:
  50.     TrieNode *root;
  52. };
  54. class Solution {
  55. public:
  56.     vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
  57.         Trie trie;
  58.         for (string &w : words) {
  59.             trie.insert(w);
  60.         }
  61.         vector<string> res;
  62.         trie.search(res, board);
  63.         return res;
  64.     }
  65. };