重新排列句子中的单词

难度: Medium

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

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

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

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

示例 1：

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

示例 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

Submission

运行时间: 32 ms

内存: 0.0 MB

class Solution:
    def arrangeWords(self, text: str) -> str:
        m = {}
        flag = False
        for s in text.split(' '):
            if not flag:
                s = s.lower()
            l = len(s)
            if l not in m:
                m[l] = []
            m[l].append(s)
        result = ''
        first = True
        for l in sorted(m.keys()):
            if not first:
                result += ' '
            else:
                first = False
            result += " ".join(m[l])
        return result.capitalize()

Explain

题解通过使用哈希表来存储相同长度的单词，键是单词的长度，值是一个列表，包含该长度的所有单词。首先，遍历输入的句子并拆分为单词。对于第一个单词，将其转换为小写（因为在最终输出中，我们将整个句子的首字母大写，其他字母小写）。然后根据单词的长度将它们添加到哈希表中的相应列表。之后，按照单词长度的升序对哈希表的键进行排序，并将相应的单词列表合并为结果字符串。最后，将结果字符串的首字母大写后返回。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def arrangeWords(self, text: str) -> str:
        m = {}  # 存储单词，键为长度，值为该长度的单词列表
        flag = False  # 用于处理第一个单词的大小写转换
        for s in text.split(' '):  # 按空格拆分单词
            if not flag:  # 第一个单词需要转换成小写
                s = s.lower()
                flag = True
            l = len(s)  # 计算单词长度
            if l not in m:
                m[l] = []  # 如果该长度未存储过，初始化列表
            m[l].append(s)  # 添加单词到对应长度的列表
        result = ''  # 结果字符串
        first = True  # 用于控制结果字符串的首个单词前不加空格
        for l in sorted(m.keys()):  # 按长度排序
            if not first:
                result += ' '  # 除首个外，单词间加空格
            else:
                first = False
            result += ' '.join(m[l])  # 加入当前长度的所有单词
        return result.capitalize()  # 首字母大写后返回

Explore

在原始句子中，通常第一个单词的首字母是大写的，为了统一处理（即不区分原文中的大小写），需要将第一个单词转换为小写。这样处理后，所有单词的格式将统一，便于排序和组合。最终在输出结果时，我们希望句子作为一个整体呈现标准的句子格式，即首字母大写，其余字母小写，这样符合一般书写习惯和语法规则。

在使用哈希表的情况下，每个键对应的值是一个列表，这个列表会按照单词被遍历到的顺序存储相同长度的单词。因此，对于每一个特定的长度，单词的相对顺序（即它们在原句中的顺序）会被保留。当把这些单词合并到结果字符串时，它们会按原始顺序出现，只是被按长度重新组织了。

在构建最终的结果字符串时，如果在每个单词前统一添加空格，那么结果字符串的开头将出现一个不必要的空格。这会导致格式上的错误，因为标准的句子不应该以空格开始。因此，特别处理第一个单词，前面不加空格，是为了确保结果字符串格式正确，符合一般的书写习惯。

虽然哈希表和列表的组合在本算法中已经能够有效地处理问题，但使用优先队列（或最小堆）也是一个可能的选择。优先队列可以直接按单词长度排序插入元素，这样在构建结果字符串时可以更高效地处理。然而，这种方法需要额外处理相同长度单词的顺序问题，可能需要一个复合数据结构（如优先队列中的元素是另一个结构，比如列表或队列，以保持同长度单词的插入顺序）。