{"id":1294,"date":"2017-12-20T08:23:52","date_gmt":"2017-12-20T16:23:52","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=1294"},"modified":"2018-01-01T16:53:20","modified_gmt":"2018-01-02T00:53:20","slug":"leetcode-748-shortest-completing-word","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/string\/leetcode-748-shortest-completing-word\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 748. Shortest Completing Word"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode  748. Shortest Completing Word  - \u5237\u9898\u627e\u5de5\u4f5c EP138\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/vHzPkqpPiWk?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<p>\u9898\u76ee\u5927\u610f: \u7ed9\u4f60\u4e00\u4e2a\u7531\u5b57\u6bcd\u548c\u6570\u5b57\u7ec4\u6210\u8f66\u724c\u3002\u53e6\u5916\u7ed9\u4f60\u4e00\u4e9b\u5355\u8bcd\uff0c\u8ba9\u4f60\u627e\u4e00\u4e2a\u6700\u77ed\u7684\u5355\u8bcd\u80fd\u591f\u8986\u76d6\u4f4f\u8f66\u724c\u4e2d\u7684\u5b57\u6bcd\uff08\u4e0d\u8003\u8651\u5927\u5c0f\u5199\uff09\u3002\u5982\u679c\u6709\u591a\u4e2a\u89e3\uff0c\u8f93\u51fa\u7b2c\u4e00\u4e2a\u89e3\u3002<\/p>\n<p><strong>Problem:<\/strong><\/p>\n<p>Find the minimum length word from a given dictionary\u00a0<code>words<\/code>, which has all the letters from the string\u00a0<code>licensePlate<\/code>. Such a word is said to\u00a0<i>complete<\/i>\u00a0the given string\u00a0<code>licensePlate<\/code><\/p>\n<p>Here, for letters we ignore case. For example,\u00a0<code>\"P\"<\/code>\u00a0on the\u00a0<code>licensePlate<\/code>\u00a0still matches\u00a0<code>\"p\"<\/code>\u00a0on the word.<\/p>\n<p>It is guaranteed an answer exists. If there are multiple answers, return the one that occurs first in the array.<\/p>\n<p>The license plate might have the same letter occurring multiple times. For example, given a\u00a0<code>licensePlate<\/code>\u00a0of\u00a0<code>\"PP\"<\/code>, the word\u00a0<code>\"pair\"<\/code>\u00a0does not complete the\u00a0<code>licensePlate<\/code>, but the word\u00a0<code>\"supper\"<\/code>\u00a0does.<\/p>\n<p><b>Example 1:<\/b><\/p>\n<pre class=\"\">Input: licensePlate = \"1s3 PSt\", words = [\"step\", \"steps\", \"stripe\", \"stepple\"]\r\nOutput: \"steps\"\r\nExplanation: The smallest length word that contains the letters \"S\", \"P\", \"S\", and \"T\".\r\nNote that the answer is not \"step\", because the letter \"s\" must occur in the word twice.\r\nAlso note that we ignored case for the purposes of comparing whether a letter exists in the word.\r\n<\/pre>\n<p><b>Example 2:<\/b><\/p>\n<pre class=\"\">Input: licensePlate = \"1s3 456\", words = [\"looks\", \"pest\", \"stew\", \"show\"]\r\nOutput: \"pest\"\r\nExplanation: There are 3 smallest length words that contains the letters \"s\".\r\nWe return the one that occurred first.\r\n<\/pre>\n<p><b>Note:<\/b><\/p>\n<ol>\n<li><code>licensePlate<\/code>\u00a0will be a string with length in range\u00a0<code>[1, 7]<\/code>.<\/li>\n<li><code>licensePlate<\/code>\u00a0will contain digits, spaces, or letters (uppercase or lowercase).<\/li>\n<li><code>words<\/code>\u00a0will have a length in the range\u00a0<code>[10, 1000]<\/code>.<\/li>\n<li>Every\u00a0<code>words[i]<\/code>\u00a0will consist of lowercase letters, and have length in range\u00a0<code>[1, 15]<\/code>.<\/li>\n<\/ol>\n<p><strong>Idea:<\/strong><\/p>\n<p>Hashtable<\/p>\n<p><strong>Solution:<\/strong><\/p>\n<p>C++<\/p>\n<p>Time complexity: \u65f6\u95f4\u590d\u6742\u5ea6 O(N*26), N is number of words.<\/p>\n<p>Space complexity: \u7a7a\u95f4\u590d\u6742\u5ea6 O(26) = O(1)<\/p>\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Runtime: 15 ms\r\nclass Solution {\r\npublic:\r\n    string shortestCompletingWord(string licensePlate, vector&lt;string&gt;&amp; words) {\r\n        vector&lt;int&gt; l(26, 0);\r\n        for (const char ch : licensePlate)\r\n            if (isalpha(ch)) ++l[tolower(ch) - 'a'];\r\n        string ans;\r\n        int min_l = INT_MAX;\r\n        for (const string&amp; word : words) {\r\n            if (word.length() &gt;= min_l) continue;\r\n            if (!matches(l, word)) continue;\r\n            min_l = word.length();\r\n            ans = word;\r\n        }\r\n        return ans;\r\n    }\r\nprivate:\r\n    bool matches(const vector&lt;int&gt;&amp; l, const string&amp; word) {\r\n        vector&lt;int&gt; c(26, 0);\r\n        for (const char ch : word)\r\n            ++c[tolower(ch) - 'a'];        \r\n        for (int i = 0; i &lt; 26; ++i)\r\n            if (c[i] &lt; l[i]) return false;\r\n        return true;\r\n    }\r\n};<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u9898\u76ee\u5927\u610f: \u7ed9\u4f60\u4e00\u4e2a\u7531\u5b57\u6bcd\u548c\u6570\u5b57\u7ec4\u6210\u8f66\u724c\u3002\u53e6\u5916\u7ed9\u4f60\u4e00\u4e9b\u5355\u8bcd\uff0c\u8ba9\u4f60\u627e\u4e00\u4e2a\u6700\u77ed\u7684\u5355\u8bcd\u80fd\u591f\u8986\u76d6\u4f4f\u8f66\u724c\u4e2d\u7684\u5b57\u6bcd\uff08\u4e0d\u8003\u8651\u5927\u5c0f\u5199\uff09\u3002\u5982\u679c\u6709\u591a\u4e2a\u89e3\uff0c\u8f93\u51fa\u7b2c\u4e00\u4e2a\u89e3\u3002 Problem: Find the minimum length word from a given dictionary\u00a0words, which has all the letters from the string\u00a0licensePlate. Such a word is said&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[163,70,47],"tags":[24],"class_list":["post-1294","post","type-post","status-publish","format-standard","hentry","category-easy","category-hashtable","category-string","tag-frequency","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1294","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=1294"}],"version-history":[{"count":7,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1294\/revisions"}],"predecessor-version":[{"id":1439,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1294\/revisions\/1439"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=1294"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=1294"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=1294"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}