{"id":4914,"date":"2019-03-02T08:03:46","date_gmt":"2019-03-02T16:03:46","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4914"},"modified":"2019-03-02T08:08:17","modified_gmt":"2019-03-02T16:08:17","slug":"leetcode-30-substring-with-concatenation-of-all-words","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-30-substring-with-concatenation-of-all-words\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 30. Substring with Concatenation of All Words"},"content":{"rendered":"\n<p>You are given a string,&nbsp;<strong>s<\/strong>, and a list of words,&nbsp;<strong>words<\/strong>, that are all of the same length. Find all starting indices of substring(s) in&nbsp;<strong>s<\/strong>that is a concatenation of each word in&nbsp;<strong>words<\/strong>&nbsp;exactly once and without any intervening characters.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted crayon:false\"><strong>Input:\n  s =<\/strong> \"barfoothefoobarman\",\n<strong>  words = <\/strong>[\"foo\",\"bar\"]\n<strong>Output:<\/strong> <code>[0,9]<\/code>\n<strong>Explanation:<\/strong> Substrings starting at index 0 and 9 are \"barfoor\" and \"foobar\" respectively.\nThe output order does not matter, returning [9,0] is fine too.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted crayon:false\"><strong>Input:\n  s =<\/strong> \"wordgoodgoodgoodbestword\",\n<strong>  words = <\/strong>[\"word\",\"good\",\"best\",\"word\"]\n<strong>Output:<\/strong> <code>[]<\/code><\/pre>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution1: HashTable + Brute Force<\/strong><\/h2>\n\n\n\n<p>Time complexity: O((|S| &#8211; |W|*l) * |W|*l))<br>Space complexity: O(|W|*l)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\n\/\/ std::string_view running time: 128 ms, 16 MB\n\/\/ std::string running time: 156 ms, 22.4 MB\nclass Solution {\npublic:\n  vector<int> findSubstring(string s, vector<string>& words) {\n    if (words.empty() || s.empty()) return {};\n    \n    const int n = words.size();\n    const int l = words[0].length();\n    \n    if (n * l > s.length()) return {};\n    \n    std::string_view ss(s);\n    \n    std::unordered_map<std::string_view, int> expected;\n    \n    for (const string& word : words)\n      ++expected[string_view(word)];\n\n    vector<int> ans;\n    \n    for (int i = 0; i <= ss.length() - n * l; ++i) {      \n      std::unordered_map<std::string_view, int> seen;\n      int count = 0;\n      for (int j = 0; j < n; ++j) {\n        std::string_view w = ss.substr(i + j * l, l);\n        auto it = expected.find(w);\n        if (it == expected.end()) break;\n        if (++seen[w] > it->second) break;\n        ++count;\n      }\n      if (count == n) \n        ans.push_back(i);\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given a string,&nbsp;s, and a list of words,&nbsp;words, that are all of the same length. Find all starting indices of substring(s) in&nbsp;sthat is&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[70],"tags":[217,82,215,314],"class_list":["post-4914","post","type-post","status-publish","format-standard","hentry","category-hashtable","tag-hard","tag-hashtable","tag-sliding-window","tag-substring","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4914","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=4914"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4914\/revisions"}],"predecessor-version":[{"id":4917,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4914\/revisions\/4917"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4914"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4914"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4914"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}