{"id":286,"date":"2024-06-24T16:01:22","date_gmt":"2024-06-24T08:01:22","guid":{"rendered":"https:\/\/wangqianming.top\/?p=286"},"modified":"2024-06-24T16:01:22","modified_gmt":"2024-06-24T08:01:22","slug":"%e6%bb%91%e5%8a%a8%e7%aa%97%e5%8f%a31","status":"publish","type":"post","link":"https:\/\/wangqianming.top\/index.php\/2024\/06\/24\/%e6%bb%91%e5%8a%a8%e7%aa%97%e5%8f%a31\/","title":{"rendered":"\u6ed1\u52a8\u7a97\u53e31"},"content":{"rendered":"<h1>\u4e32\u8054\u6240\u6709\u5355\u8bcd\u7684\u5b50\u4e32<\/h1>\n<div class=\"elfjS\" data-track-load=\"description_content\">\n<p>\u7ed9\u5b9a\u4e00\u4e2a\u5b57\u7b26\u4e32&nbsp;<code>s<\/code><strong>&nbsp;<\/strong>\u548c\u4e00\u4e2a\u5b57\u7b26\u4e32\u6570\u7ec4&nbsp;<code>words<\/code><strong>\u3002<\/strong>&nbsp;<code>words<\/code>&nbsp;\u4e2d\u6240\u6709\u5b57\u7b26\u4e32 <strong>\u957f\u5ea6\u76f8\u540c<\/strong>\u3002<\/p>\n<p>&nbsp;<code>s<\/code><strong>&nbsp;<\/strong>\u4e2d\u7684 <strong>\u4e32\u8054\u5b50\u4e32<\/strong> \u662f\u6307\u4e00\u4e2a\u5305\u542b&nbsp;&nbsp;<code>words<\/code>&nbsp;\u4e2d\u6240\u6709\u5b57\u7b26\u4e32\u4ee5\u4efb\u610f\u987a\u5e8f\u6392\u5217\u8fde\u63a5\u8d77\u6765\u7684\u5b50\u4e32\u3002<\/p>\n<ul>\n<li>\u4f8b\u5982\uff0c\u5982\u679c&nbsp;<code>words = [\"ab\",\"cd\",\"ef\"]<\/code>\uff0c \u90a3\u4e48&nbsp;<code>\"abcdef\"<\/code>\uff0c&nbsp;<code>\"abefcd\"<\/code>\uff0c<code>\"cdabef\"<\/code>\uff0c&nbsp;<code>\"cdefab\"<\/code>\uff0c<code>\"efabcd\"<\/code>\uff0c \u548c&nbsp;<code>\"efcdab\"<\/code> \u90fd\u662f\u4e32\u8054\u5b50\u4e32\u3002&nbsp;<code>\"acdbef\"<\/code> \u4e0d\u662f\u4e32\u8054\u5b50\u4e32\uff0c\u56e0\u4e3a\u4ed6\u4e0d\u662f\u4efb\u4f55&nbsp;<code>words<\/code>&nbsp;\u6392\u5217\u7684\u8fde\u63a5\u3002<\/li>\n<\/ul>\n<p>\u8fd4\u56de\u6240\u6709\u4e32\u8054\u5b50\u4e32\u5728&nbsp;<code>s<\/code><strong>&nbsp;<\/strong>\u4e2d\u7684\u5f00\u59cb\u7d22\u5f15\u3002\u4f60\u53ef\u4ee5\u4ee5 <strong>\u4efb\u610f\u987a\u5e8f<\/strong> \u8fd4\u56de\u7b54\u6848\u3002<\/p>\n<p>&nbsp;<\/p>\n<p><strong>\u793a\u4f8b 1\uff1a<\/strong><\/p>\n<pre><strong>\u8f93\u5165\uff1a<\/strong>s = \"barfoothefoobarman\", words = [\"foo\",\"bar\"]\n<strong>\u8f93\u51fa\uff1a<\/strong><code>[0,9]<\/code>\n<strong>\u89e3\u91ca\uff1a<\/strong>\u56e0\u4e3a words.length == 2 \u540c\u65f6 words[i].length == 3\uff0c\u8fde\u63a5\u7684\u5b50\u5b57\u7b26\u4e32\u7684\u957f\u5ea6\u5fc5\u987b\u4e3a 6\u3002\n\u5b50\u4e32 \"barfoo\" \u5f00\u59cb\u4f4d\u7f6e\u662f 0\u3002\u5b83\u662f words \u4e2d\u4ee5 [\"bar\",\"foo\"] \u987a\u5e8f\u6392\u5217\u7684\u8fde\u63a5\u3002\n\u5b50\u4e32 \"foobar\" \u5f00\u59cb\u4f4d\u7f6e\u662f 9\u3002\u5b83\u662f words \u4e2d\u4ee5 [\"foo\",\"bar\"] \u987a\u5e8f\u6392\u5217\u7684\u8fde\u63a5\u3002\n\u8f93\u51fa\u987a\u5e8f\u65e0\u5173\u7d27\u8981\u3002\u8fd4\u56de [9,0] \u4e5f\u662f\u53ef\u4ee5\u7684\u3002\n<\/pre>\n<p><strong>\u793a\u4f8b 2\uff1a<\/strong><\/p>\n<pre><strong>\u8f93\u5165\uff1a<\/strong>s = \"wordgoodgoodgoodbestword\", words = [\"word\",\"good\",\"best\",\"word\"]\n<code><strong>\u8f93\u51fa\uff1a<\/strong>[]<\/code>\n<strong>\u89e3\u91ca\uff1a<\/strong>\u56e0\u4e3a<strong> <\/strong>words.length == 4 \u5e76\u4e14 words[i].length == 4\uff0c\u6240\u4ee5\u4e32\u8054\u5b50\u4e32\u7684\u957f\u5ea6\u5fc5\u987b\u4e3a 16\u3002\ns \u4e2d\u6ca1\u6709\u5b50\u4e32\u957f\u5ea6\u4e3a 16 \u5e76\u4e14\u7b49\u4e8e words \u7684\u4efb\u4f55\u987a\u5e8f\u6392\u5217\u7684\u8fde\u63a5\u3002\n\u6240\u4ee5\u6211\u4eec\u8fd4\u56de\u4e00\u4e2a\u7a7a\u6570\u7ec4\u3002\n<\/pre>\n<p><strong>\u793a\u4f8b 3\uff1a<\/strong><\/p>\n<pre><strong>\u8f93\u5165\uff1a<\/strong>s = \"barfoofoobarthefoobarman\", words = [\"bar\",\"foo\",\"the\"]\n<strong>\u8f93\u51fa\uff1a<\/strong>[6,9,12]\n<strong>\u89e3\u91ca\uff1a<\/strong>\u56e0\u4e3a words.length == 3 \u5e76\u4e14 words[i].length == 3\uff0c\u6240\u4ee5\u4e32\u8054\u5b50\u4e32\u7684\u957f\u5ea6\u5fc5\u987b\u4e3a 9\u3002\n\u5b50\u4e32 \"foobarthe\" \u5f00\u59cb\u4f4d\u7f6e\u662f 6\u3002\u5b83\u662f words \u4e2d\u4ee5 [\"foo\",\"bar\",\"the\"] \u987a\u5e8f\u6392\u5217\u7684\u8fde\u63a5\u3002\n\u5b50\u4e32 \"barthefoo\" \u5f00\u59cb\u4f4d\u7f6e\u662f 9\u3002\u5b83\u662f words \u4e2d\u4ee5 [\"bar\",\"the\",\"foo\"] \u987a\u5e8f\u6392\u5217\u7684\u8fde\u63a5\u3002\n\u5b50\u4e32 \"thefoobar\" \u5f00\u59cb\u4f4d\u7f6e\u662f 12\u3002\u5b83\u662f words \u4e2d\u4ee5 [\"the\",\"foo\",\"bar\"] \u987a\u5e8f\u6392\u5217\u7684\u8fde\u63a5\u3002<\/pre>\n<p>&nbsp;<\/p>\n<p><strong>\u63d0\u793a\uff1a<\/strong><\/p>\n<ul>\n<li><code>1 &lt;= s.length &lt;= 10<sup>4<\/sup><\/code><\/li>\n<li><code>1 &lt;= words.length &lt;= 5000<\/code><\/li>\n<li><code>1 &lt;= words[i].length &lt;= 30<\/code><\/li>\n<li><code>words[i]<\/code>&nbsp;\u548c&nbsp;<code>s<\/code> \u7531\u5c0f\u5199\u82f1\u6587\u5b57\u6bcd\u7ec4\u6210<\/li>\n<\/ul>\n<\/div>\n<pre><code class=\"language-c\">class Solution {\npublic:\n    vector&lt;int&gt; findSubstring(string s, vector&lt;string&gt;&amp; words) {\n        vector&lt;int&gt; result;\n        int wordLen = words[0].size();\n        map&lt;string,int&gt; wordMap;\n        for(string word: words){\n            if(wordMap.find(word)==wordMap.end()){\n                wordMap[word] = 1;\n            }else{\n                wordMap[word]++;\n            }\n        }\n        map&lt;string,int&gt; wordMap_s;\n\n        for(int charIndex = 0;charIndex&lt;wordLen;charIndex++){\n            for (const auto&amp; pair : wordMap) {\n                wordMap_s[pair.first] = 0;\n            }\n            int start = charIndex;\n            int end = charIndex + (wordLen*words.size());\n            if(end&gt;s.size()){\n                break;\n            }\n            for(int i = start;i&lt;end;i+=wordLen){\n                string mySubString = s.substr(i,wordLen);\n                if(wordMap_s.find(mySubString)!=wordMap_s.end()){\n                    wordMap_s[mySubString]++;\n                }\n            }\n            if(wordMap == wordMap_s){\n                result.push_back(start);\n            }\n            while(true){\n                start += wordLen;\n                end += wordLen;\n                if(end&gt;s.size()){\n                    break;\n                }\n                string mySubString_left = s.substr(start-wordLen,wordLen);\n                string mySubString_right = s.substr(end-wordLen,wordLen);\n                if(wordMap_s.find(mySubString_left)!=wordMap_s.end()){\n                    wordMap_s[mySubString_left]--;\n                }\n                if(wordMap_s.find(mySubString_right)!=wordMap_s.end()){\n                    wordMap_s[mySubString_right]++;\n                }\n                if(wordMap == wordMap_s){\n                    result.push_back(start);\n                }\n            }\n        }\n\n        return result;\n    }\n};<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u4e32\u8054\u6240\u6709\u5355\u8bcd\u7684\u5b50\u4e32 \u7ed9\u5b9a\u4e00\u4e2a\u5b57\u7b26\u4e32&nbsp;s&nbsp;\u548c\u4e00\u4e2a\u5b57\u7b26\u4e32\u6570\u7ec4&nbsp;words\u3002&nbsp;words&#038;nbs &#8230","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[11,41],"class_list":["post-286","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-c","tag-41"],"_links":{"self":[{"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/posts\/286","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/comments?post=286"}],"version-history":[{"count":1,"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/posts\/286\/revisions"}],"predecessor-version":[{"id":287,"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/posts\/286\/revisions\/287"}],"wp:attachment":[{"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/media?parent=286"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/categories?post=286"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/tags?post=286"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}