Problem overview
The function reverseWords receives a string, input, made of words separated by single spaces, and returns the words in reverse order, again separated by single spaces. For "sky is blue" the answer is "blue is sky". A word is a run of non-space characters.
Approach: two reversals
A direct approach splits the string into words, reverses the list and joins it back. It works, but it builds a list of substrings. This lesson uses a neat in-place trick instead, working on a mutable copy of the text:
- Reverse the whole string.
"sky is blue"becomes"eulb si yks". The words are now in the right order, but each one is written backward. - Reverse each word on its own.
"eulb"becomes"blue","si"becomes"is"and"yks"becomes"sky".
The spaces never move relative to the words' boundaries: the first reversal puts them in exactly the places where the final answer needs them, so the second pass only has to find each word and flip it. Both passes use the same helper, reverseRange, which reverses a stretch chars[i..j] with two pointers.
On the reversed text "eulb si yks", the first pass of the loop starts with i = 0, scans j to the space at index 4, flips indices 0 to 3 and sets i to 5. The next pass handles "si", the last one handles "yks", where j stops at the end of the slice instead of at a space.
Step by step
- Copy the string into a byte slice:
chars := []byte(input). Go strings are immutable, and the slice can be changed. - Reverse everything with
reverseRange(chars, 0, len(chars)-1), a helper that is written afterwards. - Create the pointer
iat 0. It marks where the current word starts. - Loop while
i < len(chars). Each pass of this loop handles one word. - Create
jequal toi. It will scan to the end of the word. - Advance
jto the next space with an inner loop that runs whilej < len(chars)andchars[j] != ' '. The length check comes first, so the code never reads past the end. - Increment
jinside that inner loop. - Reverse the word, which occupies indices
itoj-1, becausejis the space after it or the end of the slice. - Jump to the next word with
i = j + 1, skipping the space. - Convert back with
string(chars)and return. - Write
reverseRange: a loop that runs whilei < j, swaps the two elements withswapBytes, then doesi++andj--. - Write
swapByteswith a temporary variable: savechars[i], copychars[j]intochars[i], then put the saved value intochars[j].
The solution in Go
func reverseWords(input string) string {
chars := []byte(input)
reverseRange(chars, 0, len(chars)-1)
i := 0
for i < len(chars) {
j := i
for j < len(chars) && chars[j] != ' ' {
j++
}
reverseRange(chars, i, j-1)
i = j + 1
}
return string(chars)
}
func reverseRange(chars []byte, i, j int) {
for i < j {
swapBytes(chars, i, j)
i++
j--
}
}
func swapBytes(chars []byte, i, j int) {
temp := chars[i]
chars[i] = chars[j]
chars[j] = temp
}
The Go details worth a closer look:
- Slices are shared, parameters are copies.
reverseRangereceives a copy of the slice header, but it points at the same bytes, so its swaps change the caller's data. The integersiandjare copied by value, which is whyreverseRangecan count them up and down freely without affecting the caller's variables. - Single quotes make a byte.
' 'is a character literal, and compared with achars[j]byte it works. A string literal" "would not compile in that comparison. - Short-circuit
&&. Whenj < len(chars)is false, the right side isn't evaluated. Swapping the two conditions would panic with an index-out-of-range error at the end of the last word. - Empty ranges are fine. For an empty string,
reverseRange(chars, 0, -1)hasi < jfalse and does nothing, and the outer loop is skipped. For consecutive spaces,reverseRange(chars, i, j-1)getsj-1 < iand does nothing too. - Bytes again. The slice holds bytes, so words with non-ASCII letters would be damaged by the byte reversal. The lesson's text is plain ASCII.
Complexity
Time: O(n). The full reversal touches each byte once. In the loop, every byte is passed over by j once, and each word is reversed once, so the work for all words together is also linear.
Space: O(n). The byte slice and the result string are copies of the input. The reversals themselves happen in place with a few integers.
Edge cases and common mistakes
- A single word.
"hello"is reversed twice and comes back as"hello". - Empty string. It returns
"". - Two words.
"a b"gives"b a". - Extra spaces. The problem promises single spaces. If the input had more, the code would keep them, mirrored:
"a b"comes back as"b a", and" a b"as"b a ", so leading and trailing spaces would not be removed. - Reversing only the whole string. That leaves each word backward:
"eulb si yks". - Reversing only the words. That leaves the word order unchanged.
- Using
jinstead ofj-1. The space would be pulled into the word, and the word would swap places with it. - Forgetting
i = j + 1. The outer loop would handle the same word forever.
Testing
"sky is blue"gives"blue is sky"."the quick brown fox"gives"fox brown quick the"."a b"gives"b a"."hello"gives"hello".""gives"".