Problem overview
The method reverseWords receives a string, input, made of words separated by exactly one space. A word is a run of characters that are not spaces. The method returns a new string with the same words in the opposite order, again separated by single spaces.
For "sky is blue" the words are sky, is and blue. In reverse order they are blue, is, sky, so the answer is "blue is sky". The letters inside each word keep their order. Only the order of the words changes.
Approach: turn the words into an array
Strings can't be edited, but arrays can, and the standard library already has methods to move between the two. The plan has three moves:
- Cut the string into words, so you have an array of strings.
- Reverse the array.
- Glue the words back together with a space between them.
The statement promises exactly one space between words. That promise is what makes the plan so short. Splitting on a single space gives exactly the words, with no empty strings in between, and joining with a single space restores the original spacing.
Step by step
- Split. Call
input.split(" ")and store the result inwords, annotated asstring[]. It is declared withconst. That only stops the variable from being pointed at a different array, and the array's contents can still be rearranged. - Reverse in place.
words.reverse()rearranges the elements of the array itself. It also returns the array, but sincewordsalready refers to the same array, the return value isn't needed. - Join and return.
words.join(" ")builds one string from the elements with a single space between each pair. Return it directly.
The solution in TypeScript
class Solution {
reverseWords(input: string): string {
const words: string[] = input.split(" ");
words.reverse();
return words.join(" ");
}
}
The TypeScript details worth a closer look:
constdoes not freeze the array.constfixes which arraywordsrefers to. Callingwords.reverse()changes what is inside that array, and that is allowed. Writingwords = []afterwards would be an error.- The annotation is erased.
string[]tells the compiler whatsplitreturns, and it would infer that type anyway. In the compiled JavaScript there is no trace of it. reversemutates. Unlikesliceorjoin,reversechanges the array it is called on. That is why the second line has no assignment. Writingwords = words.reverse()would run, but it adds nothing.- The separator is a string.
split(" ")cuts at each single space.split("")with an empty string would instead cut between every character, which is a different job. jointakes the separator. Leaving it out,words.join(), would use commas instead of spaces.
Complexity
Let n be the length of input.
Time: O(n). Splitting reads every character once. Reversing the array swaps about half as many elements as there are words, which is at most n. Joining copies every character once. The three steps run one after another.
Space: O(n). The array of words holds all the characters of the input except the spaces, and the joined result holds them all again.
Edge cases and common mistakes
- A single word.
"hello"splits into an array with one element. Reversing it changes nothing, and the result is"hello". - The empty string.
"".split(" ")gives[""], an array holding one empty string, and joining it gives"". - Extra spaces. The statement rules them out, and this solution relies on that. If the input had leading, trailing or repeated spaces, splitting would produce empty strings and they would be reversed too:
" a b "would come back as" b a ". Handling such input needs extra work, such as splitting on a regular expression and filtering out the empty pieces. - Reversing the characters instead. Reversing the whole string flips the letters of every word as well:
"sky is blue"would become"eulb si yks". - Forgetting to return the joined string. The array is not a string. Returning
wordsinstead ofwords.join(" ")is a compile-time error here because the method must return astring. - Joining with the wrong separator.
join("")glues the words with nothing between them:"blueissky".
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".