Easy

题目描述

给你一个字符串 text，该字符串由若干被空格包围的单词组成。每个单词由一个或者多个小写英文字母组成，并且两个单词之间至少存在一个空格。题目测试用例保证 text 至少包含一个单词。

请你重新排列空格，使每对相邻单词之间的空格数目都相等，并尽可能最大化该数目。如果不能重新平均分配所有空格，请将多余的空格放置在字符串末尾，这意味着返回的字符串应当与原 text 字符串的长度相等。

返回重新排列空格后的字符串。

示例 1：

输入：text = "  this   is  a sentence "
输出："this   is   a   sentence"
解释：总共有 9 个空格和 4 个单词。可以将 9 个空格平均分配到相邻单词之间：9 / (4-1) = 3 个空格。

示例 2：

输入：text = " practice   makes   perfect"
输出："practice   makes   perfect "
解释：总共有 7 个空格和 3 个单词。7 / (3-1) = 3 个空格，还剩 1 个空格。多余的空格放在字符串的末尾。

提示：

  • 1 <= text.length <= 100
  • text 由小写英文字母和 ' ' 组成
  • text 中至少包含一个单词

解题思路

这道题的核心思路是重新分配字符串中的空格，使得单词间的空格数尽可能均匀分布。

解题步骤如下：

  1. 统计空格和单词数量：遍历字符串统计总空格数，同时提取所有单词。

  2. 计算空格分配方案：

    • 如果只有一个单词，所有空格都放在末尾
    • 如果有多个单词，计算每两个相邻单词间应该放置的空格数：总空格数 / (单词数-1)
    • 计算剩余空格数：总空格数 % (单词数-1)，这些空格放在字符串末尾

  3. 构建结果字符串：按照计算出的空格分配方案，将单词和空格重新组合。

时间复杂度主要在于遍历字符串和构建结果，空间复杂度取决于存储单词的空间。这种方法简洁直观，易于理解和实现。

需要注意边界情况：当只有一个单词时，所有空格都应该放在该单词后面。

代码实现

class Solution {
public:
    string reorderSpaces(string text) {
        int spaces = 0;
        vector<string> words;
        string word = "";
        
        for (char c : text) {
            if (c == ' ') {
                spaces++;
                if (!word.empty()) {
                    words.push_back(word);
                    word = "";
                }
            } else {
                word += c;
            }
        }
        if (!word.empty()) {
            words.push_back(word);
        }
        
        if (words.size() == 1) {
            return words[0] + string(spaces, ' ');
        }
        
        int spaceBetween = spaces / (words.size() - 1);
        int extraSpaces = spaces % (words.size() - 1);
        
        string result = "";
        for (int i = 0; i < words.size(); i++) {
            result += words[i];
            if (i < words.size() - 1) {
                result += string(spaceBetween, ' ');
            }
        }
        result += string(extraSpaces, ' ');
        
        return result;
    }
};

class Solution:
    def reorderSpaces(self, text: str) -> str:
        spaces = text.count(' ')
        words = text.split()
        
        if len(words) == 1:
            return words[0] + ' ' * spaces
        
        space_between = spaces // (len(words) - 1)
        extra_spaces = spaces % (len(words) - 1)
        
        result = (' ' * space_between).join(words)
        result += ' ' * extra_spaces
        
        return result

public class Solution {
    public string ReorderSpaces(string text) {
        int spaces = 0;
        List<string> words = new List<string>();
        string word = "";
        
        foreach (char c in text) {
            if (c == ' ') {
                spaces++;
                if (!string.IsNullOrEmpty(word)) {
                    words.Add(word);
                    word = "";
                }
            } else {
                word += c;
            }
        }
        if (!string.IsNullOrEmpty(word)) {
            words.Add(word);
        }
        
        if (words.Count == 1) {
            return words[0] + new string(' ', spaces);
        }
        
        int spaceBetween = spaces / (words.Count - 1);
        int extraSpaces = spaces % (words.Count - 1);
        
        string result = "";
        for (int i = 0; i < words.Count; i++) {
            result += words[i];
            if (i < words.Count - 1) {
                result += new string(' ', spaceBetween);
            }
        }
        result += new string(' ', extraSpaces);
        
        return result;
    }
}

/**
 * @param {string} text
 * @return {string}
 */
var reorderSpaces = function(text) {
    const words = text.trim().split(/\s+/);
    const totalSpaces = text.length - words.join('').length;
    
    if (words.length === 1) {
        return words[0] + ' '.repeat(totalSpaces);
    }
    
    const spaceBetween = Math.floor(totalSpaces / (words.length - 1));
    const extraSpaces = totalSpaces % (words.length - 1);
    
    let result = '';
    for (let i = 0; i < words.length; i++) {
        result += words[i];
        if (i < words.length - 1) {
            result += ' '.repeat(spaceBetween);
        }
    }
    result += ' '.repeat(extraSpaces);
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历一次字符串统计空格和提取单词，构建结果字符串也是O(n)
空间复杂度O(n)需要存储单词列表和结果字符串

相关题目