翻转单词顺序列

1. 题目描述

牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？

2. 思路

• 字符串切分
• 两次翻转

3. 实现

3.1. 字符串切分

package main

import (
	"fmt"
	"strings"
)

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * @param ReverseSentence string字符串
 * @return string字符串
 */
//时间复杂度：O(N²)
//空间复杂度：O(N),因为没有在原字符串上进行翻转，所以需要额外的空间
func ReverseSentence(s string) string {
	res := ""
	splits := strings.Split(s, " ")
	for i := len(splits) - 1; i >= 0; i-- {
		res += fmt.Sprintf("%s", splits[i])
		if i > 0 {
			res += " "
		}
	}

	return res
}

3.2. 两次翻转

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * @param ReverseSentence string字符串
 * @return string字符串
 */
func ReverseSentence(s string) string {
	if s == "" {
		return ""
	}

	//abc def
	runes := []rune(s)
	//fed cba
	reverse(runes, 0, len(runes)-1)
	left := 0
	right := 0
	for right = 0; right <= len(runes); right++ {
		if right == len(runes) || runes[right] == ' ' {
			reverse(runes, left, right-1)
			left = right + 1
		}
	}

	return string(runes)
}

func reverse(runes []rune, i int, j int) {
	for i < j {
		runes[i], runes[j] = runes[j], runes[i]
		i++
		j--
	}
}

4. 参考

• 翻转单词顺序列_牛客题霸_牛客网
• 151. 反转字符串中的单词 - 力扣（LeetCode）