leetcode
leetcode 1301 ~ 1350
重新排列句子中的单词

重新排列句子中的单词

难度:

标签:

题目描述

代码结果

运行时间: 32 ms, 内存: 0.0 MB


/*
 * 思路:
 * 1. 将句子按照空格分割成单词数组。
 * 2. 使用 Java Stream API 基于单词长度进行排序。
 * 3. 保留相同长度单词的相对顺序。
 * 4. 将排序后的单词数组重新组合成句子,并将第一个单词的首字母大写。
 */

import java.util.*;
import java.util.stream.*;

public class Solution {
    public String arrangeWords(String text) {
        // 将第一个字母变成小写
        text = text.substring(0, 1).toLowerCase() + text.substring(1);
        // 按空格分割成单词数组
        String[] words = text.split(" ");
        // 使用流排序并收集结果
        words = Arrays.stream(words)
                      .sorted(Comparator.comparingInt(String::length))
                      .toArray(String[]::new);
        // 将第一个单词的首字母变成大写
        words[0] = words[0].substring(0, 1).toUpperCase() + words[0].substring(1);
        // 重新组合成句子
        return String.join(" ", words);
    }
}

解释

方法:

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

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
为什么在处理第一个单词时需要将其转换为小写,最后再将整个结果字符串的首字母大写?
在原始句子中,通常第一个单词的首字母是大写的,为了统一处理(即不区分原文中的大小写),需要将第一个单词转换为小写。这样处理后,所有单词的格式将统一,便于排序和组合。最终在输出结果时,我们希望句子作为一个整体呈现标准的句子格式,即首字母大写,其余字母小写,这样符合一般书写习惯和语法规则。
🦆
哈希表的键是单词的长度,如果两个长度相同的单词在原句子中的顺序很重要,哈希表是否能保留这种顺序?
在使用哈希表的情况下,每个键对应的值是一个列表,这个列表会按照单词被遍历到的顺序存储相同长度的单词。因此,对于每一个特定的长度,单词的相对顺序(即它们在原句中的顺序)会被保留。当把这些单词合并到结果字符串时,它们会按原始顺序出现,只是被按长度重新组织了。
🦆
请问为什么在拼接单词到结果字符串时要特别处理第一个单词前不加空格?
在构建最终的结果字符串时,如果在每个单词前统一添加空格,那么结果字符串的开头将出现一个不必要的空格。这会导致格式上的错误,因为标准的句子不应该以空格开始。因此,特别处理第一个单词,前面不加空格,是为了确保结果字符串格式正确,符合一般的书写习惯。
🦆
在整个算法中,是否有更高效的数据结构来代替哈希表和列表的组合,以处理单词的排序和存储?
虽然哈希表和列表的组合在本算法中已经能够有效地处理问题,但使用优先队列(或最小堆)也是一个可能的选择。优先队列可以直接按单词长度排序插入元素,这样在构建结果字符串时可以更高效地处理。然而,这种方法需要额外处理相同长度单词的顺序问题,可能需要一个复合数据结构(如优先队列中的元素是另一个结构,比如列表或队列,以保持同长度单词的插入顺序)。

相关问题