{"id":140143,"date":"2020-07-20T07:11:40","date_gmt":"2020-07-19T23:11:40","guid":{"rendered":"http:\/\/4563.org\/?p=140143"},"modified":"2020-07-20T07:11:40","modified_gmt":"2020-07-19T23:11:40","slug":"leetcode-lintcode-%e9%a2%98%e8%a7%a3-google-%e9%9d%a2%e8%af%95%e9%a2%98%ef%bc%9a%e5%90%88%e6%b3%95%e7%bb%84%e5%90%88","status":"publish","type":"post","link":"http:\/\/4563.org\/?p=140143","title":{"rendered":"[leetcode\/lintcode \u9898\u89e3] Google \u9762\u8bd5\u9898\uff1a\u5408\u6cd5\u7ec4\u5408"},"content":{"rendered":"
\n
\n
\n

[leetcode\/lintcode \u9898\u89e3] Google \u9762\u8bd5\u9898\uff1a\u5408\u6cd5\u7ec4\u5408 <\/h1>\n

<\/p>\n

\n
\u8cc7\u6df1\u5927\u4f6c : hakunamatata11 <\/span> <\/i> 9<\/span> <\/div>\n
<\/div>\n<\/p><\/div>\n<\/p><\/div>\n<\/p><\/div>\n
<\/p>\n

\u7ed9\u4e00\u4e2a\u5355\u8bcds<\/code>,\u548c\u4e00\u4e2a\u5b57\u7b26\u4e32\u96c6\u5408str<\/code>\u3002\u8fd9\u4e2a\u5355\u8bcd\u6bcf\u6b21\u53bb\u6389\u4e00\u4e2a\u5b57\u6bcd\uff0c\u76f4\u5230\u5269\u4e0b\u6700\u540e\u4e00\u4e2a\u5b57\u6bcd\u3002\u6c42\u9a8c\u8bc1\u662f\u5426\u5b58\u5728\u4e00\u79cd\u5220\u9664\u7684\u987a\u5e8f\uff0c\u8fd9\u4e2a\u987a\u5e8f\u4e0b\u6240\u6709\u7684\u5355\u8bcd\u90fd\u5728str<\/code>\u4e2d\u3002\u4f8b\u5982\u5355\u8bcd\u662f\u2019abc\u2019\uff0c\u5b57\u7b26\u4e32\u96c6\u5408\u662f{\u2018a\u2019,\u2019ab\u2019,\u2019abc\u2019},\u5982\u679c\u5220\u9664\u7684\u987a\u5e8f\u662f\u2019c\u2019,\u2019b\u2019\uff0c\u90a3\u4e48\u2019abc\u2019,\u2019ab\u2019,\u2019a\u2019\u90fd\u5728\u96c6\u5408\u4e2d,\u5c31\u7b26\u5408\u6761\u4ef6\u3002\u8f93\u51fa\u8fd9\u4e2a\u7ec4\u5408\u662f\u5426\u7b26\u5408\u6761\u4ef6.<\/p>\n

    \n
  • 1<=|str[i]|,|s|<=30<\/li>\n
  • 1<=str \u4e2d\u5b57\u7b26\u4e32\u7684\u4e2a\u6570<=100<\/li>\n<\/ul>\n

    \u6837\u4f8b 1:<\/p>\n

    \u8f93\u5165\uff1as=\"abc\"\uff0cstr=[\"abc\",\"ac\",\"c\"] \u8f93\u51fa\uff1atrue \u89e3\u91ca\uff1a \u9996\u5148\"abc\"\u5728`str`\u91cc \u5220\u9664'b',\"ac\"\u5728`str`\u91cc \u5220\u9664'a',\"c\"\u5728`str`\u91cc <\/code><\/pre>\n
    \u6837\u4f8b 2:<\/p>\n
    \u8f93\u5165\uff1as=\"abc\",str=[\"abc\",\"ab\",\"c\"] \u8f93\u51fa\uff1afalse \u89e3\u91ca\uff1a \"abc\"\u5728`str`\u91cc \u63a5\u4e0b\u6765\u53ea\u80fd\u5220\u9664'c',\"ab\"\u5728`str`\u91cc \u7531\u4e8e\"a\"\u548c\"b\"\u90fd\u4e0d\u5728`str`\u91cc\uff0c\u6240\u4ee5\u8fd4\u56de false <\/code><\/pre>\n
    [\u9898\u89e3]<\/p>\n
    \u8003\u70b9\uff1a<\/p>\n
    dfs<\/p>\n
      \n
    • \u6309\u7167\u9898\u76ee\u8981\u6c42\uff0c\u9996\u5148\u4fdd\u8bc1\u539f\u4e32\u5b58\u5728\u4e8e str \u4e2d\u3002<\/li>\n
    • \u6bcf\u6b21\u62fc\u63a5\u5b57\u7b26\u4e32\uff0c\u6b63\u597d\u5220\u53bb\u4e00\u4e2a\u5b57\u7b26\u7ee7\u7eed\u641c\u7d22\u3002<\/li>\n
    • \u76f4\u81f3\u5f53\u524d\u5b57\u7b26\u4e32\u957f\u5ea6\u4e3a 1 \u8fd4\u56de\u4e3a true \u3002<\/li>\n
    • \u4f7f\u7528 TreeSet \u6807\u8bb0\uff0c\u9664\u53bb\u91cd\u590d\u5b57\u7b26\u4e32\u3002<\/li>\n<\/ul>\n
      public class Solution { \/**      * @param s:       * @param str:       * @return: Output whether this combination meets the condition *\/ Set<String> map = new TreeSet<String>(); public boolean checkWord(String s, String[] str) { \/\/ Write your code here         if (s.length() > str.length) { return false;         } if (s.length() == 0) { return true;         } return dfs(s, str);     } public boolean dfs (String s, String[] str) { int result = 0; for(int i = 0; i < str.length; i++) { if(str[i].equals(s)) {                 result = 1;             }         } if (result == 0) { return false;         } if (s.length() == 1) { return true;         } \/\/\u5f53\u524d\u7684\u5b50\u4e32\u8981\u6ca1\u88ab\u8bbf\u95ee\u8fc7\u7684         if (map.contains(s)) { return false;         } for (int i = 0; i < s.length(); i++) { \/\/\u5220\u9664\u4e00\u4e2a\u5b57\u6bcd\u540e\u7684\u4e0b\u4e00\u4e2a\u5b50\u4e32             String next = s.substring(0,i) + s.substring(i + 1); if (dfs (next,str)) { return true;             }         } \/\/\u65b0\u7684\u5b50\u4e32\u653e\u5165 map\uff0c\u4e3a\u4e4b\u540e\u5b50\u4e32\u68c0\u67e5\u8bbf\u95ee\u60c5\u51b5  map.add(s); return false;     } } <\/code><\/pre>\n
      \u6700\u540e\u518d\u7ed9\u5927\u5bb6\u63a8\u8350\u4e00\u95e8\u4f7f\u7528\u7684\u524d\u7aef\u8bfe\u7a0b\uff1a\u300aWeb \u524d\u7aef\u5de5\u7a0b\u5e08 P5-P6\u300b<\/strong><\/p>\n
      \u5982\u679c\u4f60\u4e5f\u6709\u5982\u4e0b\u7591\u60d1\u548c\u70e6\u607c<\/p>\n
        \n
      • \u6211\u4e86\u89e3\u57fa\u7840\u7684 html\/css\/js\uff0c\u4f46\u7f3a\u4e4f\u6df1\u5165\u7684\u6280\u672f\u80fd\u529b\uff0c\u9047\u5230\u95ee\u9898\u6ca1\u6709\u6709\u7ecf\u9a8c\u7684\u4eba\u6307\u70b9\u600e\u4e48\u529e\uff1f<\/li>\n
      • \u524d\u7aef\u6280\u672f\u8fed\u4ee3\u5feb\uff0c\u53ef\u662f\u81ea\u5b66\u77e5\u8bc6\u4e0d\u6210\u4f53\u7cfb\uff0c\u65e0\u6cd5\u5feb\u901f\u8ddf\u4e0a\u6280\u672f\u53d8\u5316\u8282\u594f\uff0c\u6210\u957f\u7f13\u6162\u597d\u82e6\u607c\uff1b<\/li>\n
      • \u4e00\u76f4\u5728\u91cd\u590d\u5f88\u521d\u7ea7\u7684\u5de5\u4f5c\uff0c\u7f3a\u4e4f\u9879\u76ee\u7ecf\u9a8c\uff0c\u8fbe\u4e0d\u5230\u4e00\u7ebf\u5927\u5382\u7684\u80fd\u529b\u8981\u6c42\uff0c\u4e0d\u6562\u8df3\u69fd\u2026\u2026<\/li>\n<\/ul>\n
        \u9488\u5bf9\u8fd9\u4e9b\u524d\u7aef\u540c\u5b66\u7684\u5171\u6027\u95ee\u9898\uff0c\u4e5f\u4e3a\u4e86\u5e2e\u52a9\u524d\u7aef\u65b0\u624b\u548c\u521d\u7ea7\u5de5\u4f5c\u8005\u5feb\u901f\u5efa\u7acb\u5b8c\u6574\u7684\u77e5\u8bc6\u4f53\u7cfb\uff0c\u901a\u8fc7\u5b9e\u6218\u9879\u76ee\u638c\u63e1\u524d\u7aef\u9762\u8bd5\u7684\u601d\u8def\u548c\u6280\u5de7\uff0c\u6700\u7ec8\u62ff\u5230\u50cf\u963f\u91cc\u3001\u5b57\u8282\u8df3\u52a8\u3001\u817e\u8baf\u3001\u7f8e\u56e2\u8fd9\u6837\u5927\u5382\u7684 offer \u4e5d\u7ae0\u7b97\u6cd5\u4eca\u5e74\u65b0\u5f00\u53d1\u4e86\u4e00\u95e8\u524d\u7aef\u5de5\u7a0b\u5e08\u57f9\u517b\u8bfe\u7a0b\u3002<\/p>\n
        \u4e0d\u786e\u5b9a\u597d\u4e0d\u597d\uff0c\u6765\u514d\u8d39**\u62a5\u540d\u8bd5\u542c**\u5c31\u77e5\u9053\u4e86\u3002<\/p>\n<\/p><\/div>\n
         \u5927\u4f6c\u6709\u8a71\u8aaa<\/b> (0<\/span>)        <\/div>\n
         <\/div>\n<\/p><\/div>\n<\/p><\/div>\n
          \n
        • \n","protected":false},"excerpt":{"rendered":"
          [leetcode\/lintcod…<\/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\/140143"}],"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=140143"}],"version-history":[{"count":0,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/140143\/revisions"}],"wp:attachment":[{"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=140143"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=140143"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=140143"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}