{"id":203783,"date":"2025-05-22T12:57:59","date_gmt":"2025-05-22T04:57:59","guid":{"rendered":"https:\/\/server.hk\/cnblog\/203783\/"},"modified":"2025-05-22T12:57:59","modified_gmt":"2025-05-22T04:57:59","slug":"%e5%8d%95%e8%af%8d%e6%90%9c%e7%b4%a2-ii","status":"publish","type":"post","link":"https:\/\/server.hk\/cnblog\/203783\/","title":{"rendered":"\u5355\u8bcd\u641c\u7d22 II"},"content":{"rendered":"<p><b><\/b>     <\/p>\n<h1>\u5355\u8bcd\u641c\u7d22 II<\/h1>\n<p><span style=\"cursor: pointer\"><i><\/i>\u6536\u85cf<\/span>    <\/p>\n<p>\u600e\u4e48\u5165\u95e8\u6587\u7ae0\u7f16\u7a0b\uff1f\u9700\u8981\u5b66\u4e60\u54ea\u4e9b\u77e5\u8bc6\u70b9\uff1f\u8fd9\u662f\u65b0\u624b\u4eec\u521a\u63a5\u89e6\u7f16\u7a0b\u65f6\u5e38\u89c1\u7684\u95ee\u9898\uff1b\u4e0b\u9762\u5c31\u6765\u7ed9\u5927\u5bb6\u6574\u7406\u5206\u4eab\u4e00\u4e9b\u77e5\u8bc6\u70b9\uff0c\u5e0c\u671b\u80fd\u591f\u7ed9\u521d\u5b66\u8005\u4e00\u4e9b\u5e2e\u52a9\u3002\u672c\u7bc7\u6587\u7ae0\u5c31\u6765\u4ecb\u7ecd\u300a\u5355\u8bcd\u641c\u7d22 II\u300b\uff0c\u6d89\u53ca\u5230\uff0c\u6709\u9700\u8981\u7684\u53ef\u4ee5\u6536\u85cf\u4e00\u4e0b<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/www.17golang.com\/uploads\/20241124\/17324082046742738c75c26.jpg\" class=\"aligncenter\"><\/p>\n<p>\u95ee\u9898<\/p>\n<p>\u76f4\u89c9\uff1a\u56e0\u4e3a\u6211\u4eec\u5fc5\u987b\u901a\u8fc7\u4e0a\/\u4e0b\/\u5de6\/\u53f3\u65b9\u5f0f\u904d\u5386\u6765\u627e\u5230\u5355\u8bcd\u6570\u7ec4\u4e2d\u5b58\u5728\u7684\u5355\u8bcd\uff08\u5728\u7f51\u683c\/\u677f\u4e0a\uff09\u3002<br \/> \u53ef\u4ee5\u4f7f\u7528\u56de\u6eaf\u6765\u5b8c\u6210\u904d\u5386<br \/> \u4e3a\u4e86\u641c\u7d22\u5355\u8bcd\uff0c\u6211\u4eec\u53ef\u4ee5\u4f7f\u7528 trie\uff0c\u56e0\u4e3a\u8fd9\u4e5f\u53ef\u4ee5\u901a\u8fc7\u68c0\u67e5\u6811\u4e2d\u662f\u5426\u5b58\u5728\u524d\u7f00\u6765\u5e2e\u52a9\u6211\u4eec\u8fdb\u884c\u65e9\u671f\u8bc6\u522b\u3002\u8fd9\u662f\u907f\u514d\u4e0d\u5fc5\u8981\u7684\u904d\u5386\u677f\uff08\u5373\u904d\u5386\u677f\u6ca1\u6709\u610f\u4e49\uff0c\u5982\u679c\u524d\u7f00\u4e0d\u5b58\u5728\u4e8e\u7279\u91cc\u6811\u4e2d\uff0c\u90a3\u4e48\u4f7f\u7528\u524d\u7f00\u7684\u5b57\u7b26\u4e32\u6216\u5355\u8bcd\u5f62\u5f0f\u4e5f\u4e0d\u4f1a\u51fa\u73b0\u5728\u7279\u91cc\u6811\u4e2d\uff09<\/p>\n<p>\u65b9\u6cd5\uff1a\u6211\u4eec\u5c06\u6240\u6709\u5355\u8bcd[]\u653e\u5165trie\u6811\u4e2d\uff0c\u7136\u540e\u904d\u5386\u68cb\u76d8\u4e2d\u7684\u6bcf\u4e2a\u5355\u5143\u683c(i,j)\uff0c\u5e76\u5728\u6240\u67094\u4e2a\u65b9\u5411\u4e0a\u5f62\u6210\u5404\u79cd\u5b57\u7b26\u4e32\uff0c\u7136\u540e\u5c06\u6240\u6709\u5217\u8868\u4e2d trie \u4e2d\u5b58\u5728\u7684\u5b57\u7b26\u4e32\u3002<\/p>\n<pre>class Solution {\n    public List&lt;String&gt; findWords(char[][] board, String[] words) {\n        int max = 0;\n        Trie t = new Trie();\n        for (String w : words) {\n            t.insert(w);\n        }\n\n        int arr[][] = new int[board.length][board[0].length];\n        StringBuilder str = new StringBuilder();\n\n        Set&lt;String&gt; list = new HashSet&lt;&gt;();\/\/ to have only unique strings\/words\n        for (int i = 0; i &lt; board.length; i++) {\n            for (int j = 0; j &lt; board[0].length; j++) {\n                \/\/ recursively traverse all the cells to find the words\n                traverse(i, j, board, arr, arr.length, arr[0].length, t, str, list);\n            }\n        }\n        return new ArrayList&lt;&gt;(list);\n    }\n\n    public void traverse(int i, int j, char b[][], int arr[][], int n, int m, Trie t, StringBuilder str,Set&lt;String&gt; list) {\n\n        str.append(b[i][j]);\/\/ add current cell character to form a potential prefix\/word\n        if (!t.startWith(str.toString())) {\/\/early checking of prefix before moving forward to avoid un-necessary traversal\n            str.deleteCharAt(str.length() - 1);\n            return;\n        }\n        if (t.present(str.toString()))\n            list.add(str.toString());\n\n        arr[i][j] = 1;\/\/ mark current cell visited to avoid visiting the same cell the current recursive call stack\n\n        int dirs[][] = { { 0, -1 }, { 0, 1 }, { -1, 0 }, { 1, 0 } };\/\/ left,right,up,down\n\n        for (int dir[] : dirs) {\n            int I = i + dir[0];\n            int J = j + dir[1];\n            if (I &lt; n &amp;&amp; J &lt; m &amp;&amp; I &gt;= 0 &amp;&amp; J &gt;= 0 &amp;&amp; arr[I][J] == 0) {\n                traverse(I, J, b, arr, n, m, t, str, list);\n            }\n        }\n        arr[i][j] =0;\/\/ mark unvisited \n        str.deleteCharAt(str.length()-1);\/\/ remove the last added character\n    }\n\n}\n\nclass Node {\n\n    Node node[] = new Node[26];\n    boolean flag;\n\n    public boolean isPresent(char c) {\n        return node[c - 'a'] != null;\n    }\n\n    public Node get(char c) {\n        return node[c - 'a'];\n    }\n\n    public void add(char c, Node n) {\n        node[c - 'a'] = n;\n    }\n\n    public void setFlag() {\n        this.flag = true;\n    }\n\n    public boolean getFlag() {\n        return this.flag;\n    }\n}\n\nclass Trie {\n    Node root;\n\n    public Trie() {\n        root = new Node();\n    }\n\n    public void insert(String s) {\n        Node node = root;\n        for (int i = 0; i &lt; s.length(); i++) {\n            char c = s.charAt(i);\n            if (!node.isPresent(c)) {\n                node.add(c, new Node());\n            }\n            node = node.get(c);\n        }\n        node.setFlag();\n    }\n\n    public boolean present(String s) {\n        Node node = root;\n        for (int i = 0; i &lt; s.length(); i++) {\n            char c = s.charAt(i);\n            if (!node.isPresent(c)) {\n                return false;\n            }\n            node = node.get(c);\n        }\n        return node.getFlag();\n    }\n\n    public boolean startWith(String s) {\n        Node node = root;\n        for (int i = 0; i &lt; s.length(); i++) {\n            char c = s.charAt(i);\n            if (!node.isPresent(c)) {\n                return false;\n            }\n            node = node.get(c);\n        }\n        return true;\n    }\n}\n<\/pre>\n<p>\u4eca\u5929\u5173\u4e8e\u300a\u5355\u8bcd\u641c\u7d22 II\u300b\u7684\u5185\u5bb9\u4ecb\u7ecd\u5c31\u5230\u6b64\u7ed3\u675f\uff0c\u5982\u679c\u6709\u4ec0\u4e48\u7591\u95ee\u6216\u8005\u5efa\u8bae\uff0c\u53ef\u4ee5\u5728\u516c\u4f17\u53f7\u4e0b\u591a\u591a\u56de\u590d\u4ea4\u6d41\uff1b\u6587\u4e2d\u82e5\u6709\u4e0d\u6b63\u4e4b\u5904\uff0c\u4e5f\u5e0c\u671b\u56de\u590d\u7559\u8a00\u4ee5\u544a\u77e5\uff01<\/p>\n<p>      \u7248\u672c\u58f0\u660e \u672c\u6587\u8f6c\u8f7d\u4e8e\uff1adev.to \u5982\u6709\u4fb5\u72af\uff0c\u8bf7\u8054\u7cfb\u5220\u9664<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u5355\u8bcd\u641c\u7d22 II \u6536\u85cf \u600e\u4e48\u5165\u95e8\u6587&#46;&#46;&#46;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4925],"tags":[],"class_list":["post-203783","post","type-post","status-publish","format-standard","hentry","category-4925"],"_links":{"self":[{"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/posts\/203783","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/comments?post=203783"}],"version-history":[{"count":0,"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/posts\/203783\/revisions"}],"wp:attachment":[{"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/media?parent=203783"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/categories?post=203783"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/tags?post=203783"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}