题目描述

句子 是一个用空格分隔单词的字符串。给你一个满足下述格式的句子 text：

• 句子的首字母大写。
• text 中的每个单词都用单个空格分隔。

请你重新排列 text 中的单词，使所有单词按其长度的升序排列。如果两个单词的长度相同，则保留其在原句子中的相对顺序。

请同样按上述格式返回新的句子。

样例

输入：text = "Leetcode is cool"
输出："Is cool leetcode"
解释：句子中共有 3 个单词，长度为 8 的 "Leetcode" ，长度为 2 的 "is" 以及长度为 4 的 "cool" 。
输出需要按单词的长度升序排列，新句子中的第一个单词首字母需要大写。

输入：text = "Keep calm and code on"
输出："On and keep calm code"
解释：输出的排序情况如下：
"On" 2 个字母。
"and" 3 个字母。
"keep" 4 个字母，因为存在长度相同的其他单词，所以它们之间需要保留在原句子中的相对顺序。
"calm" 4 个字母。
"code" 4 个字母。

输入：text = "To be or not to be"
输出："To be or to be not"

限制

• text 以大写字母开头，然后包含若干小写字母以及单词间的单个空格。
• 1 <= text.length <= 10^5

算法

(模拟) $O(n \log n)$

1. 将句子拆分为若干个单词，注意将首字母变为小写。
2. 进行稳定排序 stable_sort。
3. 拼成新的句子，注意将首字母大写。

时间复杂度

• 拆分单词的时间复杂度为 $O(n)$，排序的时间复杂度为 $O(n \log n)$，组合新句子的时间复杂度为 $O(n)$。
• 故总时间复杂度为 $O(n \log n)$。

空间复杂度

• 需要额外 $O(n)$ 的空间存储单词数组。

C++ 代码

class Solution {
public:
    string arrangeWords(string text) {
        vector<string> words;
        int n = text.size();
        string cur;

        for (int i = 0; i < n; i++) {
            if (text[i] == ' ') {
                words.push_back(cur);
                cur.clear();
            } else {
                if (text[i] >= 'A' && text[i] <= 'Z')
                    text[i] = text[i] - 'A' + 'a';
                cur += text[i];
            }
        }

        words.push_back(cur);

        stable_sort(words.begin(), words.end(), [](const string &x, const string &y) {
            return x.size() < y.size();
        });

        string ans;
        int m = words.size();
        words[0][0] = words[0][0] - 'a' + 'A';
        for (int i = 0; i < m; i++) {
            ans += words[i];
            if (i < m - 1)
                ans += " ";
        }

        return ans;
    }
};