{"id":1864,"date":"2018-02-24T20:17:13","date_gmt":"2018-02-25T04:17:13","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=1864"},"modified":"2018-03-04T10:42:18","modified_gmt":"2018-03-04T18:42:18","slug":"leetcode-791-custom-sort-string","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/string\/leetcode-791-custom-sort-string\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 791. Custom Sort String"},"content":{"rendered":"<p>\u9898\u76ee\u5927\u610f\uff1a\u7ed9\u4f60\u5b57\u7b26\u7684\u987a\u5e8f\uff0c\u8ba9\u4f60\u6392\u5e8f\u4e00\u4e2a\u5b57\u7b26\u4e32\u3002<\/p>\n<p><code>S<\/code>\u00a0and\u00a0<code>T<\/code>\u00a0are strings composed of lowercase letters. In\u00a0<code>S<\/code>, no letter occurs more than once.<\/p>\n<p><code>S<\/code>\u00a0was sorted in some custom order previously. We want to permute the characters of\u00a0<code>T<\/code>\u00a0so that they match the order that\u00a0<code>S<\/code>\u00a0was sorted. More specifically, if\u00a0<code>x<\/code>\u00a0occurs before\u00a0<code>y<\/code>\u00a0in\u00a0<code>S<\/code>, then\u00a0<code>x<\/code>\u00a0should occur before\u00a0<code>y<\/code>\u00a0in the returned string.<\/p>\n<p>Return any permutation of\u00a0<code>T<\/code>\u00a0(as a string) that satisfies this property.<\/p>\n<pre class=\"\">Example :\r\nInput: \r\nS = \"cba\"\r\nT = \"abcd\"\r\nOutput: \"cbad\"\r\nExplanation: \r\n\"a\", \"b\", \"c\" appear in S, so the order of \"a\", \"b\", \"c\" should be \"c\", \"b\", and \"a\". \r\nSince \"d\" does not appear in S, it can be at any position in T. \"dcba\", \"cdba\", \"cbda\" are also valid outputs.\r\n<\/pre>\n<p>&nbsp;<\/p>\n<p><strong>Note:<\/strong><\/p>\n<ul>\n<li><code>S<\/code>\u00a0has length at most\u00a0<code>26<\/code>, and no character is repeated in\u00a0<code>S<\/code>.<\/li>\n<li><code>T<\/code>\u00a0has length at most\u00a0<code>200<\/code>.<\/li>\n<li><code>S<\/code>\u00a0and\u00a0<code>T<\/code>\u00a0consist of lowercase letters only.<\/li>\n<\/ul>\n<p><strong>Solution 1: HashTable + Sorting<\/strong><\/p>\n<ol>\n<li>Store the order of char in a hashtable<\/li>\n<li>Sort the string based on the order<\/li>\n<\/ol>\n<p>Time complexity: O(nlogn)<\/p>\n<p>Space complexity: O(128)<\/p>\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 2 ms\r\nclass Solution {\r\npublic:\r\n  string customSortString(string S, string T) {\r\n    vector&lt;int&gt; order(128, INT_MAX);\r\n    int i = 0;\r\n    for (char c: S) \r\n      if (order[c] == INT_MAX) order[c] = ++i;\r\n    std::sort(T.begin(), T.end(), [&amp;order](const char c1, const char c2){ \r\n      return order[c1] &lt; order[c2]; \r\n    });\r\n    return T;\r\n  }\r\n};<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u9898\u76ee\u5927\u610f\uff1a\u7ed9\u4f60\u5b57\u7b26\u7684\u987a\u5e8f\uff0c\u8ba9\u4f60\u6392\u5e8f\u4e00\u4e2a\u5b57\u7b26\u4e32\u3002 S\u00a0and\u00a0T\u00a0are strings composed of lowercase letters. In\u00a0S, no letter occurs more than once. S\u00a0was sorted in some custom order previously. We want to permute&#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,47],"tags":[82,177,15],"class_list":["post-1864","post","type-post","status-publish","format-standard","hentry","category-hashtable","category-string","tag-hashtable","tag-medium","tag-sorting","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1864","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=1864"}],"version-history":[{"count":6,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1864\/revisions"}],"predecessor-version":[{"id":1870,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1864\/revisions\/1870"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=1864"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=1864"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=1864"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}