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 不含前导或尾随空格

解题思路

这道题的核心思路是根据每个单词末尾的数字来恢复原始的句子顺序。

解题思路：

  1. 分割字符串：首先将输入的字符串按空格分割成单词数组
  2. 提取位置信息：每个单词的最后一个字符是该单词在原句子中的位置（1-9）
  3. 排序重构：根据位置信息对单词进行排序，然后去掉末尾的数字
  4. 拼接结果：将排序后的单词用空格连接成最终结果

具体步骤：

  • 遍历分割后的单词，提取每个单词的位置数字和实际内容
  • 使用数组或列表存储，索引对应原始位置
  • 最后按顺序拼接所有单词

这种方法的优势是直接利用位置信息进行定位，避免了复杂的排序操作，时间复杂度低且实现简洁。

代码实现

class Solution {
public:
    string sortSentence(string s) {
        vector<string> words(10);
        stringstream ss(s);
        string word;
        
        while (ss >> word) {
            int pos = word.back() - '0';
            words[pos] = word.substr(0, word.length() - 1);
        }
        
        string result;
        for (int i = 1; i <= 9; i++) {
            if (!words[i].empty()) {
                if (!result.empty()) result += " ";
                result += words[i];
            }
        }
        
        return result;
    }
};

class Solution:
    def sortSentence(self, s: str) -> str:
        words = s.split()
        result = [''] * len(words)
        
        for word in words:
            pos = int(word[-1]) - 1
            result[pos] = word[:-1]
        
        return ' '.join(result)

public class Solution {
    public string SortSentence(string s) {
        string[] words = s.Split(' ');
        string[] result = new string[words.Length];
        
        foreach (string word in words) {
            int pos = word[word.Length - 1] - '1';
            result[pos] = word.Substring(0, word.Length - 1);
        }
        
        return string.Join(" ", result);
    }
}

var sortSentence = function(s) {
    const words = s.split(' ');
    const result = new Array(words.length);
    
    for (const word of words) {
        const pos = parseInt(word[word.length - 1]) - 1;
        result[pos] = word.slice(0, -1);
    }
    
    return result.join(' ');
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)n 为字符串长度，需要遍历一次字符串进行分割和处理
空间复杂度O(n)需要额外的数组空间存储单词，空间大小与输入规模成正比

相关题目