557. 反转字符串中的单词 III

题目描述

输入一个字符串 s，它由若干个单词组成，相邻单词之间用一个空格隔开。

把每个单词内部的字符顺序颠倒过来。单词之间的先后次序不变，空格的位置也不变。

返回处理后的字符串。

示例 1

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

解释：四个单词各自倒序，单词次序保持不变。

示例 2

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

解释："Mr" 变成 "rM"，"Ding" 变成 "gniD"。

数据范围

1 <= s.length <= 5 * 10^4
s 由可打印的 ASCII 字符组成。
s 开头和末尾都没有空格。
s 中至少有一个单词。
单词之间都恰好用一个空格分隔。

解题思路

用 start 标记当前单词的开头，另一个指针 end 向右走到空格或末尾，[start, end - 1] 就是一个完整的单词。对这个区间用左右双指针 i、j 交换反转，然后把 start 设为 end + 1，跳过空格处理下一个单词。空格本身始终不动。

为什么正确

start 左边的所有单词都已反转完毕；每个空格都留在原来的下标上。

复杂度分析

时间 O(n)，end 把每个字符扫一遍，反转时每个字符最多交换一次；额外空间 O(n)。

易错点

处理最后一个单词时，它后面没有空格，end 会停在 n，必须让内层循环先判断 end < n 再读 t[end]；另外不要把整个字符串反转，那会把单词顺序也颠倒。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def reverseWords(self, s: str) -> str:
        t = list(s)
        n = len(t)
        start = 0
        while start < n:
            end = start
            while end < n and t[end] != ' ':
                end += 1
            i, j = start, end - 1
            while i < j:
                t[i], t[j] = t[j], t[i]
                i += 1
                j -= 1
            start = end + 1
        return ''.join(t)

class Solution {
    public String reverseWords(String s) {
        char[] t = s.toCharArray();
        int n = t.length;
        int start = 0;
        while (start < n) {
            int end = start;
            while (end < n && t[end] != ' ') {
                end++;
            }
            int i = start, j = end - 1;
            while (i < j) {
                char c = t[i]; t[i] = t[j]; t[j] = c;
                i++;
                j--;
            }
            start = end + 1;
        }
        return new String(t);
    }
}

class Solution {
public:
    string reverseWords(string s) {
        string t = s;
        int n = t.size();
        int start = 0;
        while (start < n) {
            int end = start;
            while (end < n && t[end] != ' ') {
                end++;
            }
            int i = start, j = end - 1;
            while (i < j) {
                swap(t[i], t[j]);
                i++;
                j--;
            }
            start = end + 1;
        }
        return t;
    }
};

func reverseWords(s string) string {
	t := []byte(s)
	n := len(t)
	start := 0
	for start < n {
		end := start
		for end < n && t[end] != ' ' {
			end++
		}
		i, j := start, end-1
		for i < j {
			t[i], t[j] = t[j], t[i]
			i++
			j--
		}
		start = end + 1
	}
	return string(t)
}

var reverseWords = function(s) {
    const t = s.split('');
    const n = t.length;
    let start = 0;
    while (start < n) {
        let end = start;
        while (end < n && t[end] !== ' ') {
            end++;
        }
        let i = start, j = end - 1;
        while (i < j) {
            [t[i], t[j]] = [t[j], t[i]];
            i++;
            j--;
        }
        start = end + 1;
    }
    return t.join('');
};

function reverseWords(s: string): string {
    const t = s.split('');
    const n = t.length;
    let start = 0;
    while (start < n) {
        let end = start;
        while (end < n && t[end] !== ' ') {
            end++;
        }
        let i = start, j = end - 1;
        while (i < j) {
            [t[i], t[j]] = [t[j], t[i]];
            i++;
            j--;
        }
        start = end + 1;
    }
    return t.join('');
}

载入编辑器，自己跑一遍 →

双指针专题的其他题目

查看双指针全部题目 →