{"id":2828,"date":"2020-01-29T15:26:29","date_gmt":"2020-01-29T07:26:29","guid":{"rendered":"http:\/\/www.sniper97.cn\/?p=2828"},"modified":"2020-01-29T15:26:29","modified_gmt":"2020-01-29T07:26:29","slug":"%e3%80%90leetcode%e3%80%910030-%e4%b8%b2%e8%81%94%e6%89%80%e6%9c%89%e5%8d%95%e8%af%8d%e7%9a%84%e5%ad%90%e4%b8%b2","status":"publish","type":"post","link":"http:\/\/www.sniper97.cn\/index.php\/note\/algorithm\/2828\/","title":{"rendered":"\u3010LeetCode\u30110030 \u4e32\u8054\u6240\u6709\u5355\u8bcd\u7684\u5b50\u4e32"},"content":{"rendered":"\n<p><a href=\"https:\/\/leetcode-cn.com\/problems\/substring-with-concatenation-of-all-words\/\">https:\/\/leetcode-cn.com\/problems\/substring-with-concatenation-of-all-words\/<\/a><\/p>\n\n\n<pre class=\"wp-block-preformatted\"># -*- coding:utf-8 -*-\n<em>\n<\/em>class Solution(object):\n    def findSubstring(self, s, words):\n        <em>\"\"\"\n        <\/em><strong><em>:type<\/em><\/strong><em> s: str\n        <\/em><strong><em>:type<\/em><\/strong><em> words: List[str]\n        <\/em><strong><em>:rtype<\/em><\/strong><em>: List[int]\n        \"\"\"\n        <\/em>if not s or len(s) == 0 or not words or len(words) == 0:\n            return []\n        words_map, res = dict(), []\n        for i in words:\n            if i not in words_map:\n                words_map[i] = 1\n            else:\n                words_map[i] += 1\n        one_word_size = len(words[0])\n        all_words_size = len(words) * one_word_size\n        for i in range(len(s) - all_words_size + 1):\n            tmp_str, d = s[i:i + all_words_size], dict(words_map)\n            for j in range(0, len(tmp_str), one_word_size):\n                key = tmp_str[j:j + one_word_size]\n                if key in d:\n                    d[key] -= 1\n                    if d[key] == 0:\n                        del d[key]\n                else:\n                    break\n            if not d:\n                res.append(i)\n        return res\nif __name__ == '__main__':\n    s = \"barfoothefoobarman\"\n    words = [\"foo\", \"bar\"]\n    s = \"barfoofoobarthefoobarman\"\n    words = [\"bar\", \"foo\", \"the\"]\n    # s = \"lingmindraboofooowingdingbarrwingmonkeypoundcake\"\n    # words = [\"fooo\", \"barr\", \"wing\", \"ding\", \"wing\"]\n    print(Solution().findSubstring(s, words))\n<\/pre>\n\n\n<p><strong>\u601d\u8def<\/strong>\uff1a\u7c7b\u4f3c\u4e8e\u6ed1\u52a8\u7a97\u53e3\uff0c\u53d6words\u4e2d\u603b\u957f\u5ea6\u5927\u5c0f\u7684\u7a97\u53e3\uff0c\u7136\u540e\u4f9d\u6b21\u5411\u540e\u6ed1\u52a8\uff0c\u5982\u679c\u80fd\u5c06words\u4e2d\u6240\u6709\u5355\u8bcd\u5339\u914d\uff08\u4f7f\u7528\u4e00\u4e2a\u4e34\u65f6\u5b57\u5178\u4f5c\u4e3a\u662f\u5426\u53d1\u751f\u5339\u914d\u7684\u5224\u65ad\u4f9d\u636e\uff0c\u5339\u914d\u5219value-1\uff0c\u52300\u5254\u9664\uff09\uff0c\u5219\u8bb0\u5f55\u7a97\u53e3\u7684\u7d22\u5f15\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"<p>https:\/\/leetcode-cn.com\/problems\/substring-with-co [&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":1410,"_links":{"self":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/posts\/2828"}],"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=2828"}],"version-history":[{"count":0,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/posts\/2828\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/media?parent=2828"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/categories?post=2828"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/tags?post=2828"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}