{"id":229879,"date":"2020-12-19T12:04:49","date_gmt":"2020-12-19T04:04:49","guid":{"rendered":"http:\/\/4563.org\/?p=229879"},"modified":"2020-12-19T12:04:49","modified_gmt":"2020-12-19T04:04:49","slug":"leetcode-lintcode-%e9%a2%98%e8%a7%a3-google-%e9%9d%a2%e8%af%95%e9%a2%98%ef%bc%9a%e5%8d%95%e8%af%8d%e7%9f%a9%e9%98%b5","status":"publish","type":"post","link":"http:\/\/4563.org\/?p=229879","title":{"rendered":"[leetcode\/lintcode \u9898\u89e3] Google \u9762\u8bd5\u9898\uff1a\u5355\u8bcd\u77e9\u9635"},"content":{"rendered":"<div>\n<div>\n<div>\n<h1>                  [leetcode\/lintcode \u9898\u89e3] Google \u9762\u8bd5\u9898\uff1a\u5355\u8bcd\u77e9\u9635               <\/h1>\n<p> <\/p>\n<div>\n<div> <span>\u8cc7\u6df1\u5927\u4f6c : zzzrf <\/span>  <span><i><\/i> 4<\/span> <\/div>\n<div> <\/div>\n<\/p><\/div>\n<\/p><\/div>\n<\/p><\/div>\n<div isfirst=\"1\"> <\/p>\n<h3>\u63cf\u8ff0<\/h3>\n<p>\u7ed9\u51fa\u4e00\u7cfb\u5217 ### \u4e0d\u91cd\u590d\u7684\u5355\u8bcd\uff0c\u627e\u51fa\u6240\u6709\u7528\u8fd9\u4e9b\u5355\u8bcd\u80fd\u6784\u6210\u7684 \u5355\u8bcd\u77e9\u9635\u3002 \u4e00\u4e2a\u6709\u6548\u7684\u5355\u8bcd\u77e9\u9635\u662f\u6307, \u5982\u679c\u4ece\u7b2c k \u884c\u8bfb\u51fa\u6765\u7684\u5355\u8bcd\u548c\u7b2c k \u5217\u8bfb\u51fa\u6765\u7684\u5355\u8bcd\u76f8\u540c(0 &lt;= k &lt; max(numRows, numColumns))\uff0c\u90a3\u4e48\u5c31\u662f\u4e00\u4e2a\u5355\u8bcd\u77e9\u9635. \u4f8b\u5982\uff0c\u5355\u8bcd\u5e8f\u5217\u4e3a [&#8220;ball&#8221;,&#8221;area&#8221;,&#8221;lead&#8221;,&#8221;lady&#8221;] ,\u6784\u6210\u4e00\u4e2a\u5355\u8bcd\u77e9\u9635\u3002\u56e0\u4e3a\u5bf9\u4e8e\u6bcf\u4e00\u884c\u548c\u6bcf\u4e00\u5217\uff0c\u8bfb\u51fa\u6765\u7684\u5355\u8bcd\u90fd\u662f\u76f8\u540c\u7684\u3002<\/p>\n<pre><code>b a l l a r e a l e a d l a d y <\/code><\/pre>\n<p>\u5728\u7ebf\u8bc4\u6d4b\u5730\u5740<\/p>\n<p>\u73b0\u5728\u81f3\u5c11\u6709\u4e00\u4e2a\u5355\u8bcd\u5e76\u4e14\u4e0d\u591a\u4e8e 1000 \u4e2a\u5355\u8bcd \u6240\u6709\u7684\u5355\u8bcd\u90fd\u6709\u76f8\u540c\u7684\u957f\u5ea6 \u5355\u8bcd\u7684\u957f\u5ea6\u6700\u77ed\u4e3a 1 \u6700\u957f\u4e3a 5 \u6bcf\u4e00\u4e2a\u5355\u8bcd\u5747\u7531\u5c0f\u5199\u5b57\u6bcd\u7ec4\u6210<\/p>\n<h3>\u6837\u4f8b 1:<\/h3>\n<pre><code>\u8f93\u5165: [\"area\",\"lead\",\"wall\",\"lady\",\"ball\"] \u8f93\u51fa: [[\"wall\",\"area\",\"lead\",\"lady\"],[\"ball\",\"area\",\"lead\",\"lady\"]]  \u89e3\u91ca: \u8f93\u51fa\u5305\u542b \u4e24\u4e2a\u5355\u8bcd\u77e9\u9635\uff0c\u8fd9\u4e24\u4e2a\u77e9\u9635\u7684\u8f93\u51fa\u7684\u987a\u5e8f\u6ca1\u6709\u5f71\u54cd(\u53ea\u8981\u6c42\u77e9\u9635\u5185\u90e8\u6709\u5e8f)\u3002 <\/code><\/pre>\n<h3>\u6837\u4f8b 2:<\/h3>\n<pre><code>\u8f93\u5165: [\"abat\",\"baba\",\"atan\",\"atal\"] \u8f93\u51fa:  [[\"baba\",\"abat\",\"baba\",\"atan\"],[\"baba\",\"abat\",\"baba\",\"atal\"]] <\/code><\/pre>\n<h3>\u7b97\u6cd5\uff1aDFS+hashmap<\/h3>\n<p>\u679a\u4e3e dfs, \u5982\u679c\u4e24\u4e2a\u5355\u8bcd\u80fd\u4f9d\u6b21\u653e\u5728\u4e00\u8d77\uff0c\u90a3\u4e48\u4e8c\u8005\u5c31\u6709\u4e00\u6761\u8fb9\u76f8\u8fde\u3002\u53ef\u5206\u4e24\u79cd\u60c5\u51b5\u526a\u679d\uff1a1.\u5728\u653e\u4e0b\u4e00\u4e2a\u5355\u8bcd\u7684\u65f6\u5019\uff0c\u76f4\u63a5\u4ece\u4e4b\u524d\u653e\u8fc7\u7684\u5355\u8bcd\u91cc\u8ba1\u7b97\u4e00\u4e2a\u524d\u7f00 prefix \u51fa\u6765\uff0c\u4e0b\u4e00\u6b65\u53ea\u653e\u5e26\u6709\u8be5\u524d\u7f00\u7684\u5355\u8bcd\u3002\u5176\u4e2d\u4f7f\u7528 hashmap \u6765\u5b9e\u73b0\u8bb0\u5f55\u524d\u7f00\u7684\u529f\u80fd\u30022.\u5728\u7b2c\u4e00\u6b65\u9009\u62e9\u597d\u4e4b\u540e\uff0c\u540c\u65f6\u68c0\u67e5\u5982\u679c\u653e\u4e86\u8fd9\u4e2a\u5355\u8bcd\u540e\uff0c\u5b57\u5178\u4e2d\u662f\u5426\u542b\u6709\u8fdb\u4e00\u6b65\u524d\u7f00\u7684\u5355\u8bcd\uff0c\u6ca1\u6709\u7684\u8bdd\u4e5f\u4e0d\u80fd\u653e\u7b2c\u4e00\u6b65\u9009\u51fa\u7684\u5355\u8bcd<\/p>\n<p>\u6839\u636e\u6837\u4f8b\u4e3e\u4f8b\uff1awords = [\u201carea\u201d,\u201clead\u201d,\u201cwall\u201d,\u201clady\u201d,\u201cball\u201d]<\/p>\n<p>\u6211\u4eec\u5148\u8ba9 prefix[&#8220;&#8221;]=words, \u7136\u540e\u5c06\u6240\u6709\u5b57\u7b26\u4e32\u7684\u7684\u524d\u7f00\u548c\u5bf9\u5e94\u5b57\u7b26\u4e32\u90fd\u653e\u5230 prefix \u8fd9\u4e2a hash table \u91cc\u9762<\/p>\n<p>squares[][]\u8fd9\u4e2a\u91cc\u9762\u662f\u653e\u5df2\u7ecf\u627e\u597d\u7684 words\uff0c\u5f53\u5df2\u7ecf\u627e\u5230\u4e86 wordLen \u4e2a\u5b57\u7b26\u4e32\u4e4b\u540e\u5c31\u662f\u4e00\u4e2a\u53ef\u884c\u89e3\u4e86\uff0c\u653e\u5230 results \u91cc\u9762<\/p>\n<p>checkPrefix(index, nextWord)\u8fd9\u4e2a\u51fd\u6570\u662f\u5728\u7b2c index+1 \u5230 wordLen \u7684\u5217\u4e2d\uff0c\u627e\u7b2c 0 \u5230 index &#8211; 1 \u884c\u4e2d\u627e\u5230 pre \u524d\u7f00<\/p>\n<p>\u6bd4\u5982 squares = [wall, area, lead]\uff0cindex = 3\uff0c\u6b64\u65f6 pre \u904d\u5386 squares\uff0c\u628a\u6bcf\u4e2a\u5b57\u7b26\u4e32\u7684\u7b2c 3 \u4e2a\u5b57\u7b26\u62fc\u8d77\u6765\uff0c\u5373 lad\uff0c\u7136\u540e\u518d\u4e0e\u8fd8\u4e0d\u5728 squares \u4e2d\u7684\u5b57\u7b26\u4e32(lady, ball)\u7684\u7b2c 3 \u4e2a\u5b57\u7b26\u6328\u4e2a\u62fc\u8d77\u6765\uff0c\u770b\u662f\u4e0d\u662f\u5728 prefix \u91cc\u9762\u3002\u8fd9\u91cc\u5148\u5904\u7406 lady, lad+y=lady\uff0c\u5728 prefix \u91cc\u9762\uff0c\u6240\u4ee5 squares=[wall, area, lead, lady]\u662f\u4e00\u4e2a\u53ef\u884c\u89e3\uff0c\u653e\u5165 results \u3002<\/p>\n<h3>\u590d\u6742\u5ea6\u5206\u6790<\/h3>\n<p>\u65f6\u95f4\u590d\u6742\u5ea6 O(1000^5) \u7ecf\u8fc7\u526a\u679d\uff0c\u9884\u8ba1\u590d\u6742\u5ea6 26^2 \u7a7a\u95f4\u590d\u6742\u5ea6 O(n^2) \u5b58\u50a8 hash \u7b49\u5173\u7cfb<\/p>\n<pre><code>public class Solution {     \/*      * @param words: a set of words without duplicates      * @return: all word squares      *\/     private int wordlen = 0;     private Map&lt;String,List&lt;String&gt;&gt; prefix = new HashMap&lt;String,List&lt;String&gt;&gt;();     private List&lt;String&gt; squares = new ArrayList&lt;String&gt;();     private List&lt;List&lt;String&gt;&gt; res = new ArrayList&lt;List&lt;String&gt;&gt;();     public List&lt;List&lt;String&gt;&gt; wordSquares(String[] words) {         if (words == null || words.length == 0) {             return res;         }         initprefixes(words);         wordlen = words[0].length();         dfs(0);         return res;     }     \/\/\u9884\u5904\u7406\u5f97\u5230 prefix     private void initprefixes(String[] words) {         for(String word : words) {             prefix.putIfAbsent(\"\", new ArrayList&lt;&gt;());             prefix.get(\"\").add(word);             String pre = \"\";             for (int i = 0; i &lt; word.length(); i++) {                 pre += word.charAt(i);                 prefix.putIfAbsent(pre, new ArrayList&lt;&gt;());                 prefix.get(pre).add(word);             }         }     }     private boolean checkPrefix(int index,String next) {          for(int i = index + 1; i &lt; wordlen; i++) {             String pre = \"\";             for (int j = 0; j &lt; index; ++j) {                 pre += squares.get(j).charAt(i);             }             pre += next.charAt(i);               if(!prefix.containsKey(pre)) {                 return false;             }         }           return true;     }     private void dfs(int index) {         if (index == wordlen) {             res.add(new ArrayList&lt;&gt;(squares));             return ;         }         String pre = \"\";         for (int i = 0;i &lt; index;i++) {             pre += squares.get(i).charAt(index);         }         List&lt;String&gt; matchedWords = new ArrayList&lt;String&gt;(prefix.get(pre));         int m = matchedWords.size();         for (int i = 0;i &lt; m;i++) {             \/\/\u627e\u5230 pre \u524d\u7f00             if (!checkPrefix(index, matchedWords.get(i))) {                 continue;             }             squares.add(matchedWords.get(i));             dfs(index + 1);             squares.remove(squares.size() - 1);         }     } } <\/code><\/pre>\n<p>\u66f4\u591a\u9898\u89e3\u53c2\u8003<\/p>\n<\/p><\/div>\n<div> <b>\u5927\u4f6c\u6709\u8a71\u8aaa<\/b> (<span>0<\/span>)        <\/div>\n<div> <\/div>\n<\/p><\/div>\n<\/p><\/div>\n<ul>\n<li>\n","protected":false},"excerpt":{"rendered":"<p>[leetcode\/lintcod&hellip;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[],"tags":[],"_links":{"self":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/229879"}],"collection":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=229879"}],"version-history":[{"count":0,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/229879\/revisions"}],"wp:attachment":[{"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=229879"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=229879"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=229879"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}