{"id":6764,"date":"2020-05-16T21:31:04","date_gmt":"2020-05-17T04:31:04","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6764"},"modified":"2020-05-16T21:31:54","modified_gmt":"2020-05-17T04:31:54","slug":"leetcode-1451-rearrange-words-in-a-sentence","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/string\/leetcode-1451-rearrange-words-in-a-sentence\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1451. Rearrange Words in a Sentence"},"content":{"rendered":"\n<p>Given a sentence&nbsp;<code>text<\/code>&nbsp;(A&nbsp;<em>sentence<\/em>&nbsp;is a string of space-separated words) in the following format:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>First letter is in upper case.<\/li><li>Each word in&nbsp;<code>text<\/code>&nbsp;are separated by a single space.<\/li><\/ul>\n\n\n\n<p>Your task is to rearrange the words in text such that&nbsp;all words are rearranged in an increasing order of their lengths. If two words have the same length, arrange them in their original order.<\/p>\n\n\n\n<p>Return the new text&nbsp;following the format shown above.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> text = \"Leetcode is cool\"\n<strong>Output:<\/strong> \"Is cool leetcode\"\n<strong>Explanation: <\/strong>There are 3 words, \"Leetcode\" of length 8, \"is\" of length 2 and \"cool\" of length 4.\nOutput is ordered by length and the new first word starts with capital letter.\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:<\/strong> text = \"Keep calm and code on\"\n<strong>Output:<\/strong> \"On and keep calm code\"\n<strong>Explanation: <\/strong>Output is ordered as follows:\n\"On\" 2 letters.\n\"and\" 3 letters.\n\"keep\" 4 letters in case of tie order by position in original text.\n\"calm\" 4 letters.\n\"code\" 4 letters.\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> text = \"To be or not to be\"\n<strong>Output:<\/strong> \"To be or to be not\"\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>text<\/code>&nbsp;begins with a capital letter and then contains lowercase letters and single space between words.<\/li><li><code>1 &lt;= text.length &lt;= 10^5<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Stable sort<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(nlogn)<br>Space complexity: O(n)<\/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\nclass Solution {\npublic:\n  string arrangeWords(string text) {\n    vector<string> words{\"\"};\n    for (char c : text) {\n      if (c == ' ') \n        words.push_back(\"\");\n      else\n        words.back() += c;\n    }\n    \n    words[0][0] = tolower(words[0][0]);\n    \n    stable_sort(begin(words), end(words), [](const auto& w1, const auto& w2){\n      return w1.length() < w2.length();\n    });\n    \n    string ans;\n    for (const string&#038; word : words) {\n      if (!ans.empty()) ans += ' ';\n      ans += word;\n    }\n    ans[0] = toupper(ans[0]);\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given a sentence&nbsp;text&nbsp;(A&nbsp;sentence&nbsp;is a string of space-separated words) in the following format: First letter is in upper case. Each word in&nbsp;text&nbsp;are separated by a single&#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":[177,598,4],"class_list":["post-6764","post","type-post","status-publish","format-standard","hentry","category-string","tag-medium","tag-stable-sort","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6764","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=6764"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6764\/revisions"}],"predecessor-version":[{"id":6766,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6764\/revisions\/6766"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6764"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6764"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6764"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}