Reverse Word Order

1. Problem Description

NowCoder recently got a new employee named Fish. Every morning, he always carries an English magazine and writes some sentences in a notebook. His colleague Cat is quite interested in what Fish writes. One day, Cat borrowed it and tried to read it, but could not understand the meaning. For example, “student. a am I”. Later he realized that Fish had reversed the order of the words in the sentence; the correct sentence should be “I am a student.” Cat is not good at reversing the words one by one. Can you help him?

2. Approach

• Split the string
• Reverse twice

3. Implementation

3.1. Split the String

package main

import (
	"fmt"
	"strings"
)

/**
 * The class name, method name, and parameter names in the code have already been specified. Do not modify them; directly return the value required by the method.
 *
 * @param ReverseSentence string
 * @return string
 */
// Time complexity: O(N²)
// Space complexity: O(N), because the reversal is not performed in place on the original string, so extra space is required
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. Reverse Twice

package main

/**
 * The class name, method name, and parameter names in the code have already been specified. Do not modify them; directly return the value required by the method.
 *
 * @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. References

• Reverse Word Order - NowCoder
• 151. Reverse Words in a String - LeetCode