1859-将句子排序

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

我们可以给一个句子添加 从 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 不包含任何前导或者后缀空格。

方法一：维护有序的单词数组

思路与算法

我们用字符串数组 arr 来保存每个位置的单词，并遍历乱序字符串 s。每当遍历到数字时，我们会将数字前的单词填入 arr 的对应位置。

与此同时，我们统计单词的数量。最终，我们按要求从 arr 中构造顺序的句子并返回。

代码

[sol1-C++]

class Solution {
public:
    string sortSentence(string s) {
        vector<string> arr(9);   // 单词数组
        string tmp = "";   // 当前单词
        int n = 0;   // 单词数量
        // 遍历字符串
        for (auto c: s){
            if (c >= '0' && c <= '9'){
                // 如果为数字，计算对应的单词数组下标，将单词放入对应位置，并清空当前单词
                // 数组下标为 0 开头，位置索引为 1 开头
                arr[c-'0'-1] = tmp;
                tmp.clear();
                ++n;
            }
            else if (c != ' '){
                // 如果为字母，更新当前单词
                tmp.push_back(c);
            }
        }
        string res = arr[0];   // 原本顺序的句子 
        for (int i = 1; i < n; ++i){
            res += " " + arr[i];
        }
        return res;
    }
};

[sol1-Python3]

class Solution:
    def sortSentence(self, s: str) -> str:
        s = s.split()
        n = len(s)   # 单词数量
        arr = ["" for _ in range(n)]   # 单词数组
        for wd in s:
            # 计算位置索引对应的单词数组下标，并将单词放入对应位置
            # 数组下标为 0 开头，位置索引为 1 开头
            arr[int(wd[-1])-1] = wd[:-1]
        return " ".join(arr)

复杂度分析

• 时间复杂度：O(m)，其中 m 为 s 的长度。遍历字符串、维护单词数组、输出结果的时间复杂度均为 O(m)。

• 空间复杂度：O(m)，其中 m 为 s 的长度。即为建立并维护单词数组所需的空间。