LeetCode 1451. 重新排列句子中的单词

2021-10-17 HGNULB 约 8 分钟

文章信息 6 个分类 2 个标签

分类

题目描述

✅ 1451. 重新排列句子中的单词

题意分析

输入是一个「句子」：单词之间用单个空格分隔，首字母大写、其余全小写，没有标点。要求把单词按长度从短到长重新排列，长度相同的单词必须保持它们在原句中的相对先后顺序，最后仍然按句子格式输出——单个空格分隔，整句首字母大写、其余小写。

三个条件必须同时抠死。第一，「长度相同保持原序」就是排序稳定性的要求，它决定了不能用任意排序，也不能在比较器里对等长的情况做二次排序。第二，输入句子的首字母是大写的，而它排完序后未必还在第一位，所以必须先把整句转小写，否则那个大写字母会跟着单词跑到句子中间去。第三，输出时要给新的第一个单词补上大写。

约束里的信号很温和：句子长度不超过 100 左右，单词数不多，$O(n \log n)$ 的排序绰绰有余，甚至按长度桶排也行。真正的考点不在效率，而在「稳定性 + 大小写的搬移」这两个容易翻车的语义细节。

边界：句子保证非空且至少有一个单词，所以不必担心空数组导致的首字母访问越界；题目也保证单词之间只有单个空格、首尾无空格，因此按空格切分不会产生空串。只有一个单词时，答案就是它本身重新大写首字母。

解法：稳定排序

核心思路

这道题没有需要优化的暴力解——按长度重排本身就是一次排序。真正的推导发生在「怎么让排序不破坏题目要求的两条语义」上。

第一个观察：大小写是句子级别的属性，不是单词级别的属性。原句的首字母大写只是因为它恰好排在第一位；重排之后，第一位可能换人。所以正确的做法是先把大小写「归一化」——整句转小写，让所有单词处于同一形态，排完序后再把新的第一位单词的首字母升为大写。这一步先降后升，避免了在排序过程中追踪「谁是原来的首词」。

第二个观察：「长度相同保持原序」= 稳定排序。这里要写清楚不变量：排序结束后，对任意两个长度相等的单词 u 和 v，若 u 在原句中出现得更早，则 u 在结果中也更早。Java 的对象数组版 Arrays.sort 由 API 明确保证稳定，Go 则直接使用名字就表明语义的 sort.SliceStable；比较器只比较长度，让等长元素返回“相等”。

这里依赖的是 API 的稳定性契约，而不是某个 JDK 版本当前恰好采用的排序实现。特别提醒：Java 的稳定性保证针对对象数组；Go 的 sort.Slice 不保证稳定，必须明确选择 sort.SliceStable。

剩下的就是切分与拼接：按单个空格切分成单词数组，排序，用单个空格重新连接。

正确性由稳定排序的契约直接保证：比较器使短词一定排在长词之前；长度相等时比较结果相等，稳定性保证其原相对顺序不变。排序后再统一连接并只大写新句首，得到的句子同时满足长度顺序、稳定性和大小写格式三项要求。

解题步骤

整句转小写再切分：Java 用 text.toLowerCase(Locale.ROOT)，Go 用 strings.ToLower，之后再按空格切分。固定 Locale.ROOT 可避免默认区域设置影响 ASCII 字母 I 的转换；归一化则保证原首词的大写字母不会被带到句子中间。

按长度稳定排序：比较器只比较 length()，不要在长度相等时再比较字典序或其他任何东西——那会破坏原序要求。Java 使用稳定的对象数组版 Arrays.sort；Go 使用 sort.SliceStable，不能换成不保证稳定性的 sort.Slice。

拼接成句：用单个空格连接。这一步用语言内置的 join 即可，逐个手动 += 拼接在长句上会产生 $O(n^2)$ 的复制。

首字母升为大写：对拼好的句子取第 0 个字符转大写，再接上剩余部分。因为题目保证至少有一个单词，charAt(0) 一定存在。也可以在排序后、拼接前对 words[0] 处理，效果相同。

返回结果：注意返回的是完整句子字符串，不是单词数组。

以 text = "Keep calm and code on" 走一遍。

转小写后得到 "keep calm and code on"，切分成 ["keep", "calm", "and", "code", "on"]，对应长度 [4, 4, 3, 4, 2]，原始下标依次是 0、1、2、3、4。

稳定排序按长度升序分组：长度 2 的只有 on（下标 4）；长度 3 的只有 and（下标 2）；长度 4 的有 keep（0）、calm（1）、code（3），它们必须按原下标 0 < 1 < 3 的顺序保留，即 keep、calm、code。

排序结果是 ["on", "and", "keep", "calm", "code"]，拼接成 "on and keep calm code"，首字母升大写得到 "On and keep calm code"，与期望输出一致。

反过来看两个反例：若不先转小写，原句首词 Keep 会带着大写 K 排到第三位，输出变成 "On and Keep calm code"；若用了不稳定的排序，三个长度为 4 的单词可能被打乱成 code、keep、calm，输出 "On and code keep calm"，同样判错。

代码实现

import java.util.Arrays;
import java.util.Comparator;
import java.util.Locale;

class Solution {
    public String arrangeWords(String text) {
        // 先整句转小写，避免原首词的大写字母被排到句子中间。
        String[] words = text.toLowerCase(Locale.ROOT).split(" ");
        // 对象数组版 Arrays.sort 的 API 保证稳定，等长单词保持原序。
        Arrays.sort(words, Comparator.comparingInt(String::length));

        String joined = String.join(" ", words);
        // 题目保证至少有一个单词，charAt(0) 一定存在。
        return Character.toUpperCase(joined.charAt(0)) + joined.substring(1);
    }
}

import (
	"sort"
	"strings"
)

func arrangeWords(text string) string {
	// 先整句转小写，避免原首词的大写字母被排到句子中间。
	words := strings.Split(strings.ToLower(text), " ")
	// 必须用 SliceStable：sort.Slice 不保证等长单词的相对顺序。
	sort.SliceStable(words, func(i, j int) bool {
		return len(words[i]) < len(words[j])
	})

	// 题目保证至少有一个单词，直接取首词升为大写。
	words[0] = strings.ToUpper(words[0][:1]) + words[0][1:]
	return strings.Join(words, " ")
}

复杂度分析

时间复杂度：Java 为 $O(n + m \log m)$；Go 的 sort.SliceStable 保证 $O(m \log m)$ 次比较、$O(m \log^2 m)$ 次交换，因此按标准库实现上界记为 $O(n + m \log^2 m)$。其中 $m$ 是单词数、$n$ 是句子总长度，长度比较为 $O(1)$。

空间复杂度：$O(n)$，用于小写化、切分和拼接；返回值本身也是 $O(n)$。排序所需的额外空间不改变这一量级。

关键点总结

稳定性是本题唯一的算法考点。看到「相同键值保持输入顺序」就要立刻联想到稳定排序，并确认所用 API 的契约：Java 对象数组 Arrays.sort 稳定，Go 的 sort.SliceStable 稳定，而 sort.Slice 不稳定。

把大小写当作句子级属性而非单词级属性：先统一降为小写、排完序再对新首位升为大写。这种「先归一化、后处理输出格式」的思路在字符串重排类题目里反复出现。

拼接要用 join 或 builder，不要在循环里做字符串 +=。这是字符串题的通用红线。

比较器里不要给等长单词加任何二级排序规则，那等于主动破坏题目要求的原序。

易错点总结

忘记先转小写：text = "Keep calm and code on" 会输出 "On and Keep calm code"，句中冒出一个大写 K，同时新首词也没被大写（如果只做了 words[0] 大写则是 "On and Keep calm code" 里 On 正确但 Keep 多余）。

用不稳定的排序：Go 里写 sort.Slice 而非 sort.SliceStable，"To be or not to be" 中三个长度为 2 的单词 to、be、or 可能被打乱成 be to or，输出 "Be to or to be not"，而正确答案是 "To be or to be not"。

在比较器里给等长单词加字典序兜底：同一用例会把 to be or 排成 be or to，输出 "Be or to to be not"，直接违反原序要求。

只把 words[0] 转小写或只把原首词转小写："To be or not to be" 里第二个 to 本来就是小写、第一个 To 是大写，漏转会让排序后句中残留大写 To，输出 "Be or To not to be" 之类。

排序后忘记大写新首词：输出 "on and keep calm code"，整句全小写，判错。

对原首词做大写而不是对新首词："Leetcode is cool" 排序后是 is cool leetcode，若把 leetcode 大写会得到 "is cool Leetcode"，正确答案是 "Is cool leetcode"。

用 split("\\s+") 且句子首尾可能有空格：本题保证没有首尾空格，但换成有空格的变体时 Java 的 split 会产出一个空串元素，words[0] 是 ""，words[0][:1] 在 Go 里直接 panic、Java 的 charAt(0) 抛越界。

Go 里写 words[0][0] = ... 试图原地改字符串：Go 的 string 不可变，编译期就会报 cannot assign。必须用切片重新拼接或转成 []byte。

Go 里用 strings.Title 做首字母大写：该函数已被废弃且会把每个单词的首字母都大写，"on and keep" 变成 "On And Keep"，全句判错。

在循环里用 += 拼接结果串：每次拼接都重新分配并复制整串，句子较长时退化为 $O(n^2)$；应当用 String.join / strings.Join 或 StringBuilder。

相似题目

题目	难度	考察点
937. 重新排列日志文件	中等	同样要求「同类保持原序」，但排序键是多级的（类型、内容、标识符）
791. 自定义字符串排序	中等	排序键来自外部给定的字母优先级表，未出现的字符还要单独安置
451. 根据字符出现频率排序	中等	先统计频次再按频次降序，键需要额外一趟计数才能得到
179. 最大数	中等	比较器是「拼接后谁更大」，重点在证明该比较满足传递性
151. 反转字符串中的单词	中等	同为句子级重排，但要处理多余空格，且顺序是整体反转而非按键排序
56. 合并区间	中等	排序只是预处理，真正的工作是排完序后的一趟合并扫描