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

约 4 分钟
文章信息 6 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 虾皮
标签
字符串 排序

题目描述

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

image-20260929084818702

image-20260929084818811

题意分析

把句子里的所有单词按长度从小到大重新排列。长度相同的单词必须维持原来的先后顺序，不能再按字典序交换它们，也不能删除重复单词。

重排后的句子仍要满足原有的句式格式：单词之间用一个空格分隔，只有新句子的第一个字母大写，其余字母小写。原句首单词可能被移到中间，因此大小写需要跟随新位置重新处理。

解法：稳定排序

核心思路

[!blue]

先将整个句子转成小写并按空格拆分。这样每个单词都处于统一形式，原首词移动到任何位置都不会保留不合适的大写字母；长度也不受英文字母大小写转换影响。

接下来按单词长度排序。题目要求等长时保留输入顺序，这正是稳定排序的保证：比较器只比较长度，长度相同就视为相等，交给稳定算法保留相对次序，不需要额外按字典序打破平局。

Java 对象数组的 Arrays.sort 提供稳定排序保证，Go 使用 sort.SliceStable 明确满足这一条件。排序完成后，用一个空格连接单词，并把新首字母恢复成大写。Java 在连接后调整首字符，Go 在连接前调整首词，表达的是同一格式要求。

题目保证句子非空且分词格式规范，所以至少有一个单词可以处理。算法只改变单词次序和句首大小写，其他字母及每个单词的出现次数都保留。

解题步骤

  1. 将句子统一转成小写，按空格拆成单词序列。
  2. 使用稳定排序，仅比较两个单词的长度。
  3. 将新首词的第一个字母改成大写，其余字母保持小写。
  4. 使用单个空格连接全部单词；Java 也可以先连接再恢复首字母大写。
  5. 返回重新排列的句子。

代码实现

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, " ")
}

复杂度分析

  • 时间复杂度：设总字符数为 L、单词数为 W，Java 为 O(L + W log(W + 1))；Go 当前稳定排序实现的最坏上界为 O(L + W log²(W + 1))，其中额外对数来自稳定合并中的交换开销。
  • 空间复杂度：O(L)，用于分词、大小写转换及拼接缓冲，单词引用数组也被该量级覆盖。

关键点总结

[!green]

  • 等长保留原序依赖稳定性，比较器不应再按字典序改变平局顺序。
  • 先转小写再恢复新句首，避免原首词大写跟着单词移动到句中。
  • 格式处理不改变单词数量和内容，只随重排调整唯一的句首大写。

易错点总结

[!yellow]

  • 使用不保证稳定的排序：等长词可能被重新排列，不满足保留原序的要求。
  • 把字典序作为第二排序键：主动改变了等长单词次序，即使排序本身稳定也不正确。
  • 只大写新首字母，不小写原首词：原首词若移到句中，会留下多余的大写字母。
  • 统一小写后直接返回：新句首仍然需要恢复大写。
  • 拼接时多加空格：应让分隔符只出现在单词之间，不能增加首尾空格。

相似题目

题目 难度 关联与区别
937. 重新排列日志文件 中等 同样自定义排序并保留指定类别的稳定次序，本题同长度单词必须维持原先相对顺序。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/48208682
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！