Problem overview
The method reverseWords receives a string, input, made of words separated by a single space. It returns a string with the words in reverse order, again separated by single spaces. A word is a run of non-space characters, and each word keeps its own spelling.
For "sky is blue" the answer is "blue is sky".
Approach: reverse everything, then reverse each word back
One way is to split the string into words, reverse the list of words and join it back. This lesson takes another route, built from one small tool, a function that reverses part of an array in place. It is used twice.
First, reverse the entire string. The words then appear in the opposite order, which is what is wanted, but every word is spelled backwards. Second, reverse each word on its own, which spells it forwards again.
sky is blue
eulb si yks (whole string reversed)
blue is sky (each word reversed back)
Reversing a range of an array is the two-pointer technique: one pointer at each end of the range, swap, move both inward, and stop when they meet. The same helper handles the whole string and every single word, just with different ranges.
Strings are immutable in TypeScript, so the characters first go into an array with split(""), where they can be swapped, and the array is joined back at the end.
Step by step
- Split the input into characters. Declare
arrwithconstas astring[]frominput.split(""). With an empty separator,splitgives one entry per character.conststopsarrfrom being reassigned, but its elements can still change. - Reverse the whole array with
this.reverse(arr, 0, arr.length - 1), using a helper written later. - Start
iat 0. It marks the start of the current word. - Loop while
i < arr.length, one pass per word. - Start
jati. It scans forward to find where the word ends. - Move
jalong the word: in an inner loop that runs whilej < arr.lengthandarr[j] !== " ". The length check comes first, soarr[j]is never read past the end. - Add 1 to
jinside the inner loop. - Reverse the word. When the inner loop ends, the word covers indices
itoj - 1, andjis the space after it, or the end of the array. Callthis.reverse(arr, i, j - 1). - Jump over the space: set
itoj + 1, the start of the next word. - Join and return with
arr.join(""). The empty separator puts the characters back together as they are. - Write
reverse, a method with the parametersarr: string[],i: numberandj: numberthat returnsvoid. - Loop while
i < j. The indices approach each other from both ends of the range. - Swap
arr[i]andarr[j]with one destructuring assignment. The right side builds a new two-element array first, so no temporary variable is needed. - Move the indices:
i++andj--.
The solution in TypeScript
class Solution {
reverse(arr: string[], i: number, j: number): void {
while (i < j) {
[arr[i], arr[j]] = [arr[j], arr[i]];
i++;
j--;
}
}
reverseWords(input: string): string {
const arr: string[] = input.split("");
this.reverse(arr, 0, arr.length - 1);
let i = 0;
while (i < arr.length) {
let j = i;
while (j < arr.length && arr[j] !== " ") {
j++;
}
this.reverse(arr, i, j - 1);
i = j + 1;
}
return arr.join("");
}
}
The TypeScript details worth knowing:
- The array is shared.
reversereceives a reference to the same array, not a copy, so its swaps are visible inreverseWords. That is why it can returnvoid. - Parameters are local.
reversechangesiandjdirectly. Those are copies of the numbers, so the caller'siandjstay the same. - Destructuring swap.
[arr[i], arr[j]] = [arr[j], arr[i]]assigns to two array elements at once. Because the right side is evaluated first, both old values are saved before either position is overwritten. - Characters made of two code units.
split("")splits a string into UTF-16 code units, so characters such as emoji, which take two, are cut in half and come out scrambled. For ordinary letters there is no issue. - Annotations are erased.
string[],numberandvoidare compile-time information only.
Complexity
Time: O(n). The first reversal touches each character once. The scan finds every word's end, moving j over each character once. The per-word reversals together touch each character once more. Everything is a small constant number of passes.
Space: O(n). The array of characters has one entry per character of the input, and the result string is another of the same size. The reversals themselves need only a few numbers.
Edge cases and common mistakes
- A single word.
"hello"is reversed to"olleh", and then the one word is reversed back to"hello". - Empty string. The array is empty.
reverse(arr, 0, -1)doesn't loop, the outer loop doesn't run, and the result is"". - Last word. The inner loop ends because
jreachesarr.length, not at a space. The word is still reversed withj - 1as its end, andi = j + 1then ends the outer loop. - Extra spaces. The statement promises a single space between words. If an input did have two in a row, the code would keep both: for
"a b"it returns"b a", with the double space in the middle. A leading space in the input becomes a trailing one in the result. - Reversing only the words. Skipping the first, whole-string reversal keeps the words in their original order, each spelled backwards, so
"sky is blue"would become"yks si eulb".
Testing
"sky is blue"gives"blue is sky"."hello"gives"hello".""gives""."a b"gives"b a".