151. Reverse Words in a String

Problem

Given an input string, reverse the string word by word.

Example 1:

Input: "the sky is blue"
Output: "blue is sky the"

Example 2:

Input: "  hello world!  "
Output: "world! hello"
Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:

Input: "a good   example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

Note:

• A word is defined as a sequence of non-space characters.
• Input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces.
• You need to reduce multiple spaces between two words to a single space in the reversed string.

Follow up:

For C programmers, try to solve it in-place in O(1) extra space.

Problem Summary

Given a string, reverse each word in the string one by one.

Explanation:

• A word is composed of non-space characters.
• The input string may contain extra spaces at the beginning or end, but the reversed string must not include them.
• If there are extra spaces between two words, reduce the spaces between words after reversal to just one.  

Follow-up:

• Users choosing the C language are asked to try using an in-place solution with O(1) extra space complexity.

Solution Approach

• Given a string with words separated by spaces, reverse the string in terms of words.
• According to the problem statement, first split the string into individual words by spaces, then reverse the order of the words, and finally add spaces between each word.

Code

package leetcode

import "strings"

func reverseWords151(s string) string {
	ss := strings.Fields(s)
	reverse151(&ss, 0, len(ss)-1)
	return strings.Join(ss, " ")
}

func reverse151(m *[]string, i int, j int) {
	for i <= j {
		(*m)[i], (*m)[j] = (*m)[j], (*m)[i]
		i++
		j--
	}
}