{"id":2938,"date":"2020-02-14T12:26:00","date_gmt":"2020-02-14T04:26:00","guid":{"rendered":"http:\/\/www.sniper97.cn\/?p=2938"},"modified":"2020-02-14T12:26:00","modified_gmt":"2020-02-14T04:26:00","slug":"%e3%80%90leetcode%e3%80%910079%e5%89%91%e6%8c%87offer12-%e5%8d%95%e8%af%8d%e6%90%9c%e7%b4%a2%e7%9f%a9%e9%98%b5%e4%b8%ad%e7%9a%84%e8%b7%af%e5%be%84","status":"publish","type":"post","link":"http:\/\/www.sniper97.cn\/index.php\/note\/algorithm\/2938\/","title":{"rendered":"\u3010LeetCode\u30110079&amp;\u5251\u6307Offer12 \u5355\u8bcd\u641c\u7d22&amp;\u77e9\u9635\u4e2d\u7684\u8def\u5f84"},"content":{"rendered":"\n<p><a href=\"https:\/\/leetcode-cn.com\/problems\/word-search\/\">https:\/\/leetcode-cn.com\/problems\/word-search\/<\/a><\/p>\n\n\n<p><a href=\"https:\/\/leetcode-cn.com\/problems\/ju-zhen-zhong-de-lu-jing-lcof\/\">https:\/\/leetcode-cn.com\/problems\/ju-zhen-zhong-de-lu-jing-lcof\/<\/a><\/p>\n\n\n<pre class=\"wp-block-preformatted\"># -*- coding:utf-8 -*-\nclass Solution(object):\n    def exist(self, board, word):\n        <em>\"\"\"\n        <\/em><strong><em>:type<\/em><\/strong><em> board: List[List[str]]\n        <\/em><strong><em>:type<\/em><\/strong><em> word: str\n        <\/em><strong><em>:rtype<\/em><\/strong><em>: bool\n        \"\"\"\n        <\/em>n = len(board)\n        m = len(board[0])\n        def dfs(i, j, index):\n            mp[i][j] = False\n            if index == len(word):\n                return True\n            for ii, jj in [(0, 1), (0, -1), (1, 0), (-1, 0)]:\n                if 0 &lt;= i + ii &lt; n and 0 &lt;= j + jj &lt; m and board[i + ii][j + jj] == word[index] and mp[i + ii][j + jj]:\n                    if dfs(i + ii, j + jj, index + 1):\n                        return True\n            mp[i][j] = True\n            return False\n        for i in range(n):\n            for j in range(m):\n                if board[i][j] == word[0]:\n                    mp = [[True] * m for i in range(n)]\n                    if dfs(i, j, 1):\n                        return True\n        return False\nif __name__ == '__main__':\n    board = [\n        ['A', 'B', 'C', 'E'],\n        ['S', 'F', 'C', 'S'],\n        ['A', 'D', 'E', 'E']\n    ]\n    word = 'ABCB'\n    print(Solution().exist(board, word))\n<\/pre>\n\n\n<p><strong>\u601d\u8def<\/strong>\uff1a\u52a8\u5f52\u56de\u6eaf\u505a\u7684\u90fd\u6709\u70b9\u5feb\u5fd8\u4e86\u57fa\u7840\u7684\u4e86\u3002\u3002\u8fd9\u9053\u9898\u6df1\u5ea6\u4f18\u5148\u904d\u5386\uff0c\u5206\u522b\u5411\u4e0a\u4e0b\u5de6\u53f3\u904d\u5386\u5bfb\u627e\u76ee\u6807\u5b57\u7b26\u4e32\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"<p>https:\/\/leetcode-cn.com\/problems\/word-search\/ http [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_mi_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[10],"tags":[],"views":1985,"_links":{"self":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/posts\/2938"}],"collection":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/comments?post=2938"}],"version-history":[{"count":0,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/posts\/2938\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/media?parent=2938"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/categories?post=2938"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/tags?post=2938"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}