Problem overview
The method reverseWords(input: String) receives a sentence in which words are separated by exactly one space. It returns the same words in the opposite order, again separated by single spaces. For "sky is blue" the result is "blue is sky". Each word keeps its own spelling: only the order of the words changes.
Approach: reverse everything, then reverse each word
Building a list of words and joining it backwards would work, but this lesson practises a classic in-place trick that needs only two ingredients: a way to reverse part of an array, and two reversals.
- Reverse the whole string. The words end up in the opposite order, but every word is spelled backwards.
- Reverse each word on its own. That puts the letters of each word back in the right order and leaves the words where they are.
On "sky is blue":
sky is blue
eulb si yks (after reversing everything)
blue is sky (after reversing each word)
Reversing the whole string moves the last word to the front, which is the order we want. Reversing a word that is already backwards spells it correctly again.
A shorter route exists in Scala: split the string on spaces, reverse the resulting array of words and join them again. It builds an array of word strings along the way. The two-reversal version works directly on one array of characters, and it shows how the same reverse helper can serve two jobs: reversing the whole text and reversing a single word.
Step by step
- Get a mutable copy. A Scala
Stringis immutable, soinput.toCharArraygives anArray[Char]namedarrthat can be changed in place. - Reverse all of
arrwith a helperreverse(arr, 0, arr.length - 1), written later. - Walk the words. A
var istarts at 0 and marks the start of the current word. The outerwhile (i < arr.length)runs once per word. - Find the end of the word. A second
var jstarts atiand moves right whilej < arr.lengthandarr(j)is not a space. The bounds check comes first, because&&stops evaluating as soon as its left side is false, soarr(j)is never read past the end. - Reverse the word. When the inner loop stops, the word occupies
itoj - 1.jis either the space after the word or the end of the array. - Jump to the next word with
i = j + 1, which skips the space. - Build the result.
new String(arr)turns the characters back into a string. As the last expression of the method, it is the return value. - Write
reverse. It takes the array and the two ends of the range. Scala parameters can't be reassigned, so it copies them intovar iandvar j, then loops whilei < j: swap the two characters, moveiright andjleft. - Write
swap. It savesarr(i)in aval temp, copiesarr(j)intoarr(i), then putstempintoarr(j). Without the saved copy, the first assignment would destroy a value.
The solution in Scala
class Solution {
def swap(arr: Array[Char], i: Int, j: Int): Unit = {
val temp = arr(i)
arr(i) = arr(j)
arr(j) = temp
}
def reverse(arr: Array[Char], iStart: Int, jStart: Int): Unit = {
var i = iStart
var j = jStart
while (i < j) {
swap(arr, i, j)
i += 1
j -= 1
}
}
def reverseWords(input: String): String = {
val arr = input.toCharArray
reverse(arr, 0, arr.length - 1)
var i = 0
while (i < arr.length) {
var j = i
while (j < arr.length && arr(j) != ' ') {
j += 1
}
reverse(arr, i, j - 1)
i = j + 1
}
new String(arr)
}
}
The Scala details worth knowing:
- Arrays are mutable, strings are not.
arris aval, so the name always refers to the same array, but its elements can change. That is whyswapandreversereturnUnitand still have an effect on the caller's array. arr(i) = xis an update. Scala indexes arrays with parentheses, and assigning to an indexed element calls the array's update operation.- No
++or--. Counters move with+= 1and-= 1. - Parameters are read-only. That is why
reversecopiesiStartandjStartinto variables before moving them. - Character comparison.
' 'is aCharliteral with single quotes. Comparing it witharr(j)by!=compares values.
Here is the loop on the reversed text "eulb si yks". At i = 0 the inner loop stops at j = 4, the space, so reverse handles indices 0 to 3 and turns eulb into blue. Then i becomes 5, j stops at 7, and si becomes is. Finally i is 8, j runs to the end at 11, and yks becomes sky. The array now reads blue is sky.
Complexity
Time: O(n). The full reversal touches each character once. The word loop moves j over each character once, and the reversals of the words together touch each character at most once more.
Space: O(n). The character array is a copy of the input. The reversing itself needs only a few integers and one temporary character.
Edge cases and common mistakes
- Empty string. The array has length 0, so
reversereceives the range 0 to -1 and does nothing, the outer loop never runs, and the result is"". - A single word.
"hello"is reversed to"olleh"and then reversed back to"hello". - The last word. The inner loop ends with
jequal toarr.length, the reversal covers up toj - 1, andi = j + 1ends the outer loop. - Extra spaces. The lesson promises single spaces. If the input had extra ones, the method would keep them in the mirrored positions:
"a b"becomes"b a", and" a"becomes"a ". - Checking
arr(j)beforej < arr.length. On the last word this reads past the end of the array and throws an exception. - Reversing
itojinstead ofitoj - 1. The space atjwould be swapped into the word. - Forgetting the first reversal. Reversing only the words leaves their order unchanged.
Testing
"sky is blue"gives"blue is sky"."hello"gives"hello"."a b"gives"b a"."one two three four"gives"four three two one".""gives"".
