Problem overview
The function reverseWords takes a String named input made of words separated by single spaces. It returns a string with the words in the opposite order, again separated by single spaces. A word is a run of characters that aren't spaces, and the letters inside each word keep their normal order.
For "sky is blue" the result is "blue is sky".
Approach: two rounds of reversing
A quick way to reverse word order is to split the string at spaces, reverse the list and join it back. This lesson does it with arrays and pointers only, using a neat trick: reverse the entire string first, then reverse each word individually.
Reversing everything puts the words in the right order, but it also spells each word backwards. Take "sky is blue":
sky is blue
eulb si yks
blue is sky
The second line is the whole string reversed: the words are in the target order, with their letters flipped. The third line comes from reversing each word on its own. The spaces stay at the same positions, because reversing a word never moves anything outside the word.
Both rounds use the same operation, "reverse a range of an array in place", so the lesson writes it once as a helper, which in turn uses a small swap helper.
The word loop on "eulb si yks" (11 characters) works like this. At i = 0, j stops at index 4, the first space, so the word is indices 0 to 3 and it becomes blue. Then i jumps to 5, where j stops at index 7, and si becomes is. Finally i is 8, j runs to 11, the array size, and yks becomes sky. Then i becomes 12 and the loop ends.
Step by step
- Copy the string into a
CharArraynamedarrwithtoCharArray(). Kotlin strings are immutable, so the work needs a mutable copy. - Reverse everything with
reverse(arr, 0, arr.size - 1). The helper is defined later. - Create
i, avarstarting at 0. It marks the start of the current word. - Loop while
i < arr.size, one iteration per word. - Create
jequal toi. It will scan forward to the end of the word. - Advance
jwhile it is inside the array andarr[j]isn't a space. The checkj < arr.sizecomes first so thatarr[j]is never read past the end. - Reverse the word. When the inner loop stops, the word spans
itoj - 1, so callreverse(arr, i, j - 1). - Jump to the next word with
i = j + 1, skipping the space atj. - Convert back with
String(arr)and return it. - Write
reversewith the parametersarr,iandj. Copyiandjintovarvariablesleftandright, since parameters can't be reassigned. - Loop while
left < right, callswap(arr, left, right), then doleft++andright--. - Write
swapwith a temporary: savearr[i]intemp, copyarr[j]intoarr[i], and puttempintoarr[j].
The solution in Kotlin
class Solution {
fun swap(arr: CharArray, i: Int, j: Int) {
val temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}
fun reverse(arr: CharArray, i: Int, j: Int) {
var left = i
var right = j
while (left < right) {
swap(arr, left, right)
left++
right--
}
}
fun reverseWords(input: String): String {
val arr = input.toCharArray()
reverse(arr, 0, arr.size - 1)
var i = 0
while (i < arr.size) {
var j = i
while (j < arr.size && arr[j] != ' ') {
j++
}
reverse(arr, i, j - 1)
i = j + 1
}
return String(arr)
}
}
Kotlin details worth knowing:
- A
Charliteral uses single quotes.' 'is the space character, while" "would be a one-characterString. Comparing aCharwith aStringusing!=doesn't compile. - Arrays are shared, not copied, when passed.
reverseandswapchange the array in place, andreverseWordssees the result. That's why they return nothing. &&short-circuits. Whenjequalsarr.size, the right side isn't evaluated, so there is no out-of-bounds read.- Inclusive ranges.
reversetreats bothiandjas part of the range, which is why the whole array is0toarr.size - 1and a word isitoj - 1. String(arr)builds a new string from the array's characters, copying them.
Complexity
Time: O(n). The whole-string reversal touches each character once. The word loop moves j over every character once and each word's reversal touches each of its characters once, so the second round is also linear.
Space: O(n). The character array is a copy of the input, and the final string is another. The reversing itself needs only a few integers and one temporary character.
Edge cases and common mistakes
- A single word.
"hello"is reversed to"olleh"and then reversed back to"hello". - Empty string. The array is empty,
reverse(arr, 0, -1)does nothing becauseleft < rightis false, the word loop doesn't run, and the result is"". - Last word. There is no space after it, so
jstops atarr.size. Reversingitoj - 1still covers it, and the finali = j + 1ends the loop. - Extra spaces. The lesson promises single spaces. If there were more, the spaces would be reversed along with the rest:
"a b"gives"b a", and a leading space moves to the end. - Reversing only the words. The words keep their order and just flip their letters. Reversing only the whole string gives backward words. Both rounds are needed.
- Passing
jinstead ofj - 1. That would include the space after the word, moving it to the front of the word.
Testing
"sky is blue"gives"blue is sky"."hello"gives"hello"."a b"gives"b a".""gives"".