{"id":4280,"date":"2018-11-10T23:33:06","date_gmt":"2018-11-11T07:33:06","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4280"},"modified":"2018-11-10T23:35:24","modified_gmt":"2018-11-11T07:35:24","slug":"leetcode-937-reorder-log-files","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/string\/leetcode-937-reorder-log-files\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 937. Reorder Log Files"},"content":{"rendered":"<h1><strong>Problem<\/strong><\/h1>\n<p><a href=\"https:\/\/leetcode.com\/problems\/reorder-log-files\/description\/\">https:\/\/leetcode.com\/problems\/reorder-log-files\/description\/<\/a><\/p>\n<p>You have an array of\u00a0<code>logs<\/code>.\u00a0 Each log is a space delimited string of words.<\/p>\n<p>For each log, the first word in each log is an alphanumeric\u00a0<em>identifier<\/em>.\u00a0 Then, either:<\/p>\n<ul>\n<li>Each word after the identifier will consist only of lowercase letters, or;<\/li>\n<li>Each word after the identifier will consist only of digits.<\/li>\n<\/ul>\n<p>We will call these two varieties of logs\u00a0<em>letter-logs<\/em>\u00a0and\u00a0<em>digit-logs<\/em>.\u00a0 It is guaranteed that each log has at least one word after its identifier.<\/p>\n<p>Reorder the logs so that all of the letter-logs come before any digit-log.\u00a0 The letter-logs are ordered lexicographically ignoring identifier, with the identifier used in case of ties.\u00a0 The digit-logs should be put in their original order.<\/p>\n<p>Return the final order of the logs.<\/p>\n<p><strong>Example 1:<\/strong><\/p>\n<pre class=\"crayon:false\"><strong>Input: <\/strong><span id=\"example-input-1-1\">[\"a1 9 2 3 1\",\"g1 act car\",\"zo4 4 7\",\"ab1 off key dog\",\"a8 act zoo\"]<\/span>\r\n<strong>Output: <\/strong><span id=\"example-output-1\">[\"g1 act car\",\"a8 act zoo\",\"ab1 off key dog\",\"a1 9 2 3 1\",\"zo4 4 7\"]<\/span>\r\n<\/pre>\n<p><strong>Note:<\/strong><\/p>\n<ol>\n<li><code>0 &lt;= logs.length &lt;= 100<\/code><\/li>\n<li><code>3 &lt;= logs[i].length &lt;= 100<\/code><\/li>\n<li><code>logs[i]<\/code>\u00a0is guaranteed to have an identifier, and a word after the identifier.<\/li>\n<\/ol>\n<h1><strong>Solution: Partition + Sort<\/strong><\/h1>\n<ol>\n<li>partition the array such that all digit logs are after all letter logs<\/li>\n<li>sort the letter logs part based on the log content<\/li>\n<\/ol>\n<p>Time complexity: O(n + aloga)<\/p>\n<p>Space complexity: O(n)<\/p>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true  \">class Solution {\r\npublic:\r\n    vector&lt;string&gt; reorderLogFiles(vector&lt;string&gt;&amp; logs) {\r\n      auto alpha_end = std::stable_partition(begin(logs),  end(logs), \r\n        [](const string&amp; log){ return isalpha(log.back()); });\r\n      std::sort(begin(logs), alpha_end, [](const string&amp; a, const string&amp; b){\r\n        return a.substr(a.find(' ')) &lt; b.substr(b.find(' '));\r\n      });\r\n      return logs;\r\n    }\r\n};<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Problem https:\/\/leetcode.com\/problems\/reorder-log-files\/description\/ You have an array of\u00a0logs.\u00a0 Each log is a space delimited string of words. For each log, the first word in each log&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[47],"tags":[150,23,4,314],"class_list":["post-4280","post","type-post","status-publish","format-standard","hentry","category-string","tag-partition","tag-sort","tag-string","tag-substring","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4280","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=4280"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4280\/revisions"}],"predecessor-version":[{"id":4284,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4280\/revisions\/4284"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4280"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4280"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4280"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}