Medium

题目描述

给你一个句子 text（句子是由空格分隔的单词组成的字符串），句子格式如下：

  • 首字母大写
  • text 中的每个单词都由单个空格分隔

你的任务是重新排列 text 中的单词，使所有单词按其长度的递增顺序重新排列。如果两个单词长度相同，则按它们在原句子中的顺序排列。

返回按上述格式重新排列的新文本。

示例 1：

输入：text = "Leetcode is cool"
输出："Is cool leetcode"
解释：共有 3 个单词，"Leetcode" 长度为 8，"is" 长度为 2，"cool" 长度为 4。
输出按长度排序，新的第一个单词以大写字母开头。

示例 2：

输入：text = "Keep calm and code on"
输出："On and keep calm code"
解释：输出按如下顺序排列：
"On" 2 个字母。
"and" 3 个字母。
"keep" 4 个字母，在长度相同的情况下按原文本中的位置排序。
"calm" 4 个字母。
"code" 4 个字母。

示例 3：

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

约束：

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

解题思路

这道题的核心思路是对单词进行稳定排序。我们需要：

  1. 分词处理：将输入的句子按空格分割成单词数组，同时记录每个单词的原始位置
  2. 大小写处理：将第一个单词转换为小写，因为排序后第一个位置可能会变化
  3. 稳定排序：按单词长度进行排序，长度相同时保持原有顺序（这是稳定排序的特性）
  4. 结果构建：将排序后的第一个单词首字母大写，然后用空格连接所有单词

关键点在于理解"稳定排序"的概念 - 当比较的元素相等时，它们的相对顺序不会改变。大多数编程语言的内置排序算法都是稳定的，这正好满足题目要求。

实现时有两种常见思路：

  • 方法一：使用 (单词长度, 原始索引) 作为排序键
  • 方法二：直接利用稳定排序的特性，只按长度排序

推荐使用方法二，因为代码更简洁且性能更好。

代码实现

class Solution {
public:
    string arrangeWords(string text) {
        text[0] = tolower(text[0]);
        vector<string> words;
        stringstream ss(text);
        string word;
        
        while (ss >> word) {
            words.push_back(word);
        }
        
        stable_sort(words.begin(), words.end(), 
                   [](const string& a, const string& b) {
                       return a.length() < b.length();
                   });
        
        if (!words.empty()) {
            words[0][0] = toupper(words[0][0]);
        }
        
        string result;
        for (int i = 0; i < words.size(); i++) {
            if (i > 0) result += " ";
            result += words[i];
        }
        
        return result;
    }
};

class Solution:
    def arrangeWords(self, text: str) -> str:
        words = text.split()
        words[0] = words[0].lower()
        
        words.sort(key=len)
        
        words[0] = words[0].capitalize()
        
        return ' '.join(words)

public class Solution {
    public string ArrangeWords(string text) {
        string[] words = text.Split(' ');
        words[0] = words[0].ToLower();
        
        Array.Sort(words, (a, b) => a.Length.CompareTo(b.Length));
        
        if (words.Length > 0) {
            words[0] = char.ToUpper(words[0][0]) + words[0].Substring(1);
        }
        
        return string.Join(" ", words);
    }
}

var arrangeWords = function(text) {
    let words = text.split(' ');
    words[0] = words[0].toLowerCase();
    
    words.sort((a, b) => a.length - b.length);
    
    words[0] = words[0].charAt(0).toUpperCase() + words[0].slice(1);
    
    return words.join(' ');
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n log n)，其中 n 是单词的数量。主要消耗在排序操作上
空间复杂度O(m)，其中 m 是字符串的总长度。需要存储分割后的单词数组