Easy

题目描述

给定一个字符串 s，在句子中反转每个单词中字符的顺序，同时仍保留空格和单词的初始顺序。

示例 1：

输入：s = "Let's take LeetCode contest"
输出："s'teL ekat edoCteeL tsetnoc"

示例 2：

输入：s = "Mr Ding"
输出："rM gniD"

约束条件：

  • 1 <= s.length <= 5 * 10^4
  • s 包含可打印的 ASCII 字符
  • s 不包含任何前导或尾随空格
  • s 中至少有一个单词
  • s 中的所有单词都由单个空格分隔

解题思路

这道题要求我们反转字符串中每个单词内部的字符顺序，但保持单词之间的相对位置不变。

解法一：分割与重构法 最直观的方法是将字符串按空格分割成单词数组，逐个反转每个单词，然后重新组合。这种方法简单易懂，但需要额外的空间存储分割后的单词。

解法二：双指针原地反转（推荐） 更高效的方法是使用双指针技术在原字符串上进行原地操作。我们遍历字符串，找到每个单词的起始和结束位置，然后使用双指针对该单词进行反转。具体步骤：

  1. 用指针 start 标记当前单词的起始位置
  2. 遍历字符串，当遇到空格或到达字符串末尾时，确定单词的结束位置
  3. 使用双指针对 [start, end] 范围内的字符进行反转
  4. 更新 start 为下一个单词的起始位置

这种方法的优势在于空间复杂度更低，且避免了字符串的多次拼接操作。

代码实现

class Solution {
public:
    string reverseWords(string s) {
        int n = s.length();
        int start = 0;
        
        for (int i = 0; i <= n; i++) {
            if (i == n || s[i] == ' ') {
                reverse(s.begin() + start, s.begin() + i);
                start = i + 1;
            }
        }
        
        return s;
    }
};

class Solution:
    def reverseWords(self, s: str) -> str:
        s = list(s)
        n = len(s)
        start = 0
        
        for i in range(n + 1):
            if i == n or s[i] == ' ':
                left, right = start, i - 1
                while left < right:
                    s[left], s[right] = s[right], s[left]
                    left += 1
                    right -= 1
                start = i + 1
        
        return ''.join(s)

public class Solution {
    public string ReverseWords(string s) {
        char[] chars = s.ToCharArray();
        int n = chars.Length;
        int start = 0;
        
        for (int i = 0; i <= n; i++) {
            if (i == n || chars[i] == ' ') {
                ReverseRange(chars, start, i - 1);
                start = i + 1;
            }
        }
        
        return new string(chars);
    }
    
    private void ReverseRange(char[] chars, int left, int right) {
        while (left < right) {
            char temp = chars[left];
            chars[left] = chars[right];
            chars[right] = temp;
            left++;
            right--;
        }
    }
}

/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
    return s.split(' ').map(word => word.split('').reverse().join('')).join(' ');
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分割重构法双指针原地反转
时间复杂度O(n)O(n)
空间复杂度O(n)O(1)*

*注：对于 Python 和 JavaScript，由于字符串不可变，需要转换为字符数组，实际空间复杂度为 O(n)

相关题目