{"id":5464,"date":"2019-08-20T15:28:28","date_gmt":"2019-08-20T22:28:28","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5464"},"modified":"2019-08-20T18:17:48","modified_gmt":"2019-08-21T01:17:48","slug":"leetcode-212-word-search-ii","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-212-word-search-ii\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 212. Word Search II"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-4-3 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 212. Word Search II - \u5237\u9898\u627e\u5de5\u4f5c EP624\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/aEEJ3xHIF5o?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p>Given a 2D board and a list of words from the dictionary, find all words in the board.<\/p>\n\n\n\n<p>Each word must be constructed from letters of sequentially adjacent cell, where &#8220;adjacent&#8221; cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.<\/p>\n\n\n\n<p><strong>Example:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> \n<strong>board <\/strong>= [\n  ['o','a','a','n'],\n  ['e','t','a','e'],\n  ['i','h','k','r'],\n  ['i','f','l','v']\n]\n<strong>words<\/strong> = <code>[\"oath\",\"pea\",\"eat\",\"rain\"]<\/code>\n\n<strong>Output:&nbsp;<\/strong><code>[\"eat\",\"oath\"]<\/code>\n<\/pre>\n\n\n\n<p><strong>Note:<\/strong><\/p>\n\n\n\n<ol class=\"wp-block-list\"><li>All inputs are consist of lowercase letters&nbsp;<code>a-z<\/code>.<\/li><li>The values of&nbsp;<code>words<\/code>&nbsp;are distinct.<\/li><\/ol>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 1: DFS<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(sum(m*n*4^l))<br>Space complexity: O(l)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua, 708 ms, 15.3 MB\nclass Solution {\npublic:\n  vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {\n    unordered_set<string> unique_words(words.begin(), words.end());\n    vector<string> ans;\n    for (const string& word : unique_words)\n      if (exist(board, word))\n        ans.push_back(word);\n    return ans;\n  }\nprivate:\n  int w;\n  int h;\n  bool exist(vector<vector<char>> &board, string word) {\n    if (board.size() == 0) return false;\n    h = board.size();\n    w = board[0].size();\n    for (int i = 0 ; i < w; i++)\n      for (int j = 0 ; j < h; j++)\n        if (search(board, word, 0, i, j)) return true;\n    return false;\n  }\n    \n  bool search(vector<vector<char>> &board, \n           const string& word, int d, int x, int y) {\n    if (x < 0 || x == w || y < 0 || y == h || word[d] != board[y][x]) \n      return false;\n\n    \/\/ Found the last char of the word\n    if (d == word.length() - 1)\n      return true;\n\n    char cur = board[y][x];\n    board[y][x] = '#'; \n    bool found = search(board, word, d + 1, x + 1, y)\n              || search(board, word, d + 1, x - 1, y)\n              || search(board, word, d + 1, x, y + 1)\n              || search(board, word, d + 1, x, y - 1);\n    board[y][x] = cur;\n    return found;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2: Trie<\/strong><\/h2>\n\n\n\n<p>Store all the words into a trie, search the board using DFS, paths must be in the trie otherwise there is no need to explore.<\/p>\n\n\n\n<p>Time complexity: O(sum(l) + 4^max(l))<br>space complexity: O(sum(l) + l)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua, 64 ms, 35.6 MB\nclass TrieNode {\npublic:\n  vector<TrieNode*> nodes;  \n  const string* word;\n  TrieNode(): nodes(26), word(nullptr) {}\n  ~TrieNode() {\n    for (auto node : nodes) delete node;\n  }  \n};\nclass Solution {\npublic:\n  vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {\n    TrieNode root;\n    \n    \/\/ Add all the words into Trie.\n    for (const string& word : words) {\n      TrieNode* cur = &root;\n      for (char c : word) {\n        auto& next = cur->nodes[c - 'a'];\n        if (!next) next = new TrieNode();\n        cur = next;\n      }\n      cur->word = &word;\n    }\n    \n    const int n = board.size();\n    const int m = board[0].size();    \n    vector<string> ans;\n    \n    function<void(int, int, TrieNode*)> walk = [&](int x, int y, TrieNode* node) {      \n      if (x < 0 || x == m || y < 0 || y == n || board[y][x] == '#')\n        return;      \n      \n      const char cur = board[y][x];\n      TrieNode* next_node = node->nodes[cur - 'a'];\n      \n      \/\/ Pruning, only expend paths that are in the trie.\n      if (!next_node) return;\n      \n      if (next_node->word) {\n        ans.push_back(*next_node->word);\n        next_node->word = nullptr;\n      }\n\n      board[y][x] = '#';\n      walk(x + 1, y, next_node);\n      walk(x - 1, y, next_node);\n      walk(x, y + 1, next_node);\n      walk(x, y - 1, next_node);\n      board[y][x] = cur;\n    };\n    \n    \/\/ Try all possible pathes.\n    for (int i = 0 ; i < n; i++)\n      for (int j = 0 ; j < m; j++)\n        walk(j, i, &#038;root);        \n        \n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>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&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[44],"tags":[33,217,42,96],"class_list":["post-5464","post","type-post","status-publish","format-standard","hentry","category-searching","tag-dfs","tag-hard","tag-search","tag-trie","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5464","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=5464"}],"version-history":[{"count":6,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5464\/revisions"}],"predecessor-version":[{"id":5471,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5464\/revisions\/5471"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5464"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5464"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5464"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}