{"id":102,"date":"2017-09-06T01:19:42","date_gmt":"2017-09-06T08:19:42","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=102"},"modified":"2019-04-09T22:23:11","modified_gmt":"2019-04-10T05:23:11","slug":"leetcode-79-word-search","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/leetcode\/leetcode-79-word-search\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 79. Word Search"},"content":{"rendered":"<div class=\"question-description\">\n<p><iframe loading=\"lazy\" title=\"LeetCode 79. Word Search - \u82b1\u82b1\u9171 \u5237\u9898\u627e\u5de5\u4f5c EP37\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/oUeGFKZvoo4?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><\/p>\n<p>Given a 2D board and a word, find if the word exists in the grid.<\/p>\n<p>The word can 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.<\/p>\n<p>For example,<br \/>\nGiven&nbsp;<b>board<\/b>&nbsp;=<\/p>\n<pre>[\n  ['A','B','C','E'],\n  ['S','F','C','S'],\n  ['A','D','E','E']\n]\n<\/pre>\n<p><b>word<\/b>&nbsp;=&nbsp;<code>\"ABCCED\"<\/code>, -&gt; returns&nbsp;<code>true<\/code>,<br \/>\n<b>word<\/b>&nbsp;=&nbsp;<code>\"SEE\"<\/code>, -&gt; returns&nbsp;<code>true<\/code>,<br \/>\n<b>word<\/b>&nbsp;=&nbsp;<code>\"ABCB\"<\/code>, -&gt; returns&nbsp;<code>false<\/code>.<\/p>\n<\/div>\n<div id=\"interviewed-div\"><\/div>\n<div><strong>Idea:<\/strong><\/div>\n<div>Search, depth first search<\/div>\n<div><\/div>\n<div><a style=\"color: #0f3647;\" href=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/79-ep37.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-106\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/79-ep37.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/79-ep37.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/79-ep37-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/79-ep37-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/79-ep37-624x351.png 624w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/div>\n<div><\/div>\n<div><strong>Solution:<\/strong><\/div>\n<div>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n<\/p>\n<pre class=\"lang:c++ decode:true\">class Solution {\npublic:\n    bool exist(vector&lt;vector&lt;char&gt;&gt; &amp;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&lt;w;i++)\n            for(int j=0;j&lt;h;j++)\n                if(search(board, word, 0, i, j)) return true;\n        return false;\n    }\n    \n    bool search(vector&lt;vector&lt;char&gt;&gt; &amp;board, \n             const string&amp; word, int d, int x, int y) {\n        if(x&lt;0 || x==w || y&lt;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] = 0; \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    }\nprivate:\n    int w;\n    int h;\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python\"># Author: Huahua, running time: 216 ms\nclass Solution:\n    def exist(self, board: List[List[str]], word: str) -&gt; bool:\n      if not board: return False\n      h, w = len(board), len(board[0])\n      \n      def search(d: int, x: int, y: int) -&gt; bool:\n        if x &lt; 0 or x == w or y &lt; 0 or y == h or word[d] != board[y][x]:\n          return False\n        if d == len(word) - 1: return True\n        \n        cur = board[y][x]\n        board[y][x] = ''\n        found = search(d + 1, x + 1, y) or search(d + 1, x - 1, y) or search(d + 1, x, y + 1) or search(d + 1, x, y - 1)\n        board[y][x] = cur\n        return found\n      \n      return any(search(0, j, i) for i in range(h) for j in range(w))      \n<\/pre>\n<\/div><\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,44],"tags":[33,42],"class_list":["post-102","post","type-post","status-publish","format-standard","hentry","category-leetcode","category-searching","tag-dfs","tag-search","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/102","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=102"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/102\/revisions"}],"predecessor-version":[{"id":5026,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/102\/revisions\/5026"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=102"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=102"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=102"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}