212. Word Search II 词语搜索之二

212. Word Search II

Difficulty: 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.

Solution

Language: C++

class TrieNode {
public:
    TrieNode *child[26];
    string str;

    explicit TrieNode() : str("") {
      for (auto &p : child)
        p = nullptr;
    }
};

class Trie {
public:
    TrieNode *root;

public:
    explicit Trie() {
      root = new TrieNode();
    }

    void insert(string s) {
      auto p = root;

      for (auto c: s) {
        int letter = c - 'a';

        if (!p->child[letter])
          p->child[letter] = new TrieNode();

        p = p->child[letter];
      }
      p->str = s;
    }
};

class Solution {
public:
    vector<string> findWords(vector<vector<char>> &board, vector<string> &words) {
      vector<string> res;

      if (words.empty() || board.empty() || board.front().empty())
        return res;

      vector<vector<bool>> visit(board.size(), vector<bool>(board[0].size()));

      Trie T;
      for (auto &c:words)
        T.insert(c);

      for (int i = 0; i < board.size(); ++i)
        for (int j = 0; j < board[i].size(); ++j) {
          auto letter = board[i][j] - 'a';
          auto p = T.root->child[letter];
          if (p)
            dfs(board, p, i, j, visit, res);
        }

      return res;
    }


    void dfs(vector<vector<char>> &board,
             TrieNode *p, // ++p
             int i, int j, // ++pos
             vector<vector<bool>> &visit,

GH1995 / leetcode-test-and-run

212. Word Search II 词语搜索之二 #42

212. Word Search II

Solution