1451.Rearrange Words in a Sentence

Tags: Medium String Sort

Links: https://leetcode.com/problems/rearrange-words-in-a-sentence/

---

Given a sentence text (A sentence is a string of space-separated words) in the following format:

• First letter is in upper case.
• Each word in text are separated by a single space.

Your task is to rearrange the words in text such that all words are rearranged in an increasing order of their lengths. If two words have the same length, arrange them in their original order.

Return the new text following the format shown above.

Example 1:

Input: text = "Leetcode is cool"
Output: "Is cool leetcode"
Explanation: There are 3 words, "Leetcode" of length 8, "is" of length 2 and "cool" of length 4.
Output is ordered by length and the new first word starts with capital letter.

Example 2:

Input: text = "Keep calm and code on"
Output: "On and keep calm code"
Explanation: Output is ordered as follows:
"On" 2 letters.
"and" 3 letters.
"keep" 4 letters in case of tie order by position in original text.
"calm" 4 letters.
"code" 4 letters.

Example 3:

Input: text = "To be or not to be"
Output: "To be or to be not"

Constraints:

• text begins with a capital letter and then contains lowercase letters and single space between words.
• 1 <= text.length <= 10^5

---

核心思路是字符串切割，如果说一定要找类似的话，那么HDU 1062 Text Reverse和UIUC的System Programming的Extreme_Edge_Cases Lab会有一定程度的接近。

时间复杂度$O(n \log n)$

class Solution {
    struct Node
    {
        string str;
        int seq;
        Node(string s, int num): str(s), seq(num) {}
        bool operator<(const Node & obj) const 
        {
            return (str.size() < obj.str.size()) 
                || (str.size() == obj.str.size() && seq < obj.seq);
        }
    };

public:
    string arrangeWords(string text) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        text[0] = tolower(text[0]);
        vector<Node> word;
        split(text, word);
        sort(word.begin(), word.end());
        string res;

        int n = word.size();
        word[0].str[0] = toupper(word[0].str[0]);
        for (int i = 0; i < n; ++i) {
            res += word[i].str;
            if (i != n - 1) res.push_back(' ');
        }

        return res;
    }

    void split(string & text, vector<Node> & word)
    {
        int cnt = 1;
        int loc = 0;
        while (text.find(" ", loc) != string::npos) {
            int pos = text.find(" ", loc);
            word.push_back(Node(text.substr(loc, pos - loc), cnt++));
            loc = pos + 1;
        }
        word.push_back(Node(text.substr(loc), cnt));
    }
};