557.Reverse-Words-In-a-String-III.md

title	date	categories	tags	publish
557. Reverse Words In a String III	2022-03-22	leetcode	array	true

1. 题目描述

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

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

示例 2:
输入： s = "God Ding"
输出："doG gniD"
 
提示：
1 <= s.length <= 5 * 104
s 包含可打印的 ASCII 字符。
s 不包含任何开头或结尾空格。
s 里 至少 有一个词。
s 中的所有单词都用一个空格隔开。

2. 题解

此题可以看做是 151 的简化版本，没有多余的空格并且字符串不会为空。可以使用快慢指针来确定单词边界，翻转每个单词。

func reverseWords(s string) string {
    b := []byte(s)
    n := len(b)
    // 使用快慢指针
    left, right := 0, 0
    for right < n {
        // find space
        for right < n && b[right] != ' ' {
            right++
        } 
        reverseByteSlice(b, left, right-1)
        right++
        left = right
    }
    
    return *(*string)(unsafe.Pointer(&b))
}

func reverseByteSlice(b []byte, start, end int) { 
    for start < end {
        // exchange
        b[start], b[end] = b[end], b[start]
        start++
        end--
    }
}

Reference

1. 557. Reverse Words In a String III