将句子排序

难度: Easy

一个句子指的是一个序列的单词用单个空格连接起来，且开头和结尾没有任何空格。每个单词都只包含小写或大写英文字母。

我们可以给一个句子添加 从 1 开始的单词位置索引 ，并且将句子中所有单词 打乱顺序 。

比方说，句子 "This is a sentence" 可以被打乱顺序得到 "sentence4 a3 is2 This1" 或者 "is2 sentence4 This1 a3" 。

给你一个 打乱顺序 的句子 s ，它包含的单词不超过 9 个，请你重新构造并得到原本顺序的句子。

示例 1：

输入：s = "is2 sentence4 This1 a3"
输出："This is a sentence"
解释：将 s 中的单词按照初始位置排序，得到 "This1 is2 a3 sentence4" ，然后删除数字。

示例 2：

输入：s = "Myself2 Me1 I4 and3"
输出："Me Myself and I"
解释：将 s 中的单词按照初始位置排序，得到 "Me1 Myself2 and3 I4" ，然后删除数字。

提示：

2 <= s.length <= 200
s 只包含小写和大写英文字母、空格以及从 1 到 9 的数字。
s 中单词数目为 1 到 9 个。
s 中的单词由单个空格分隔。
s 不包含任何前导或者后缀空格。

Submission

运行时间: 20 ms

内存: 0.0 MB

class Solution:
    def sortSentence(self, s: str) -> str:
        words = s.split(' ')
        new = []
        for i in range(len(words)):
            for word in words:
                if str(i+1) in word:
                    new.append(word.replace(str(i+1), ''))
                    break
                    
        return ' '.join(new)

Explain

这个解题思路基于两步处理。首先，将字符串s按空格分割得到单词数组。然后，根据每个单词末尾的数字（从1到9），将单词放到一个新的数组中正确的位置。数字在单词中的位置确定了单词在原句子中的顺序。这个数字随后从单词中移除，得到的单词是原始单词，无数字。最后，新数组中的单词按顺序连接起来，形成一个整理后的句子。

时间复杂度: O(n^2)

空间复杂度: O(n)

class Solution:
    def sortSentence(self, s: str) -> str:
        words = s.split(' ')  # 将句子s分割成单词数组
        new = []  # 创建一个新的数组存放正确顺序的单词
        for i in range(len(words)):  # 从0到n-1，遍历每个位置
            for word in words:  # 遍历每个单词
                if str(i+1) in word:  # 检查当前数字是否在单词中
                    new.append(word.replace(str(i+1), ''))  # 移除数字，并将单词加入新数组
                    break  # 找到正确的单词后跳出内循环
        return ' '.join(new)  # 将新数组中的单词用空格连接成句子

Explore

这种方法选择的原因是题目特定的格式要求，即每个单词的末尾带有一个数字，这个数字直接指示了单词在句子中的排序位置。使用这个数字作为排序基准，可以直接且有效地确定每个单词的正确位置，这比使用其他特征（如单词长度或字母表顺序）更为直接和符合题目要求。

算法使用了字符串的 'in' 操作来检查数字是否存在于单词中。这种方法简单且易于实现，但并不是最优的，因为它只能判断数字是否存在，却不能准确判断数字是否为单词末尾的字符。更优的方法是使用正则表达式来确保数字位于单词的末尾，或者直接检查单词末尾字符是否为目标数字。

为了避免类似的误判，应该在检查数字时确保它是单词末尾的字符。可以通过检查单词的最后一个字符是否为目标数字，而不是简单地使用 'in' 操作。这样可以确保即使单词中有重复数字，也只有正确位置的数字会被用于排序。

使用两个数组可以使逻辑更清晰，易于管理和理解。尽管可能通过原地修改数组或使用额外的数据结构（如哈希表）来优化空间复杂度，但这可能会使代码更复杂，难以维护。对于这种简单的问题，清晰和直接的解法通常更受推荐。