Problem overview
The function reverse_words takes a String called input. A word is a run of non-space characters, and words are separated by one space. The function returns a new String with the words in the opposite order, again separated by single spaces. The words themselves are not reversed.
For "sky is blue" the answer is "blue is sky".
Approach: split, reverse the list, join
The task has three natural parts: cut the text into words, reverse the order of the list of words, and glue the words back together with spaces. Rust has a tool for each part:
split_whitespace()cuts a string into words;rev()walks a sequence from the end to the start;join(" ")glues a list of strings together with a separator.
No character is moved by hand. The words are not copied while they are split: each one is a &str slice that points into input. Only the final join allocates a new string.
Step by step
- Split into words.
input.split_whitespace()produces the words one at a time, andcollect()gathers them into aVec<&str>namedwords. The annotation onwordstellscollect()what to build. - Reverse, copy the references, collect and join. This is the function's last expression.
words.iter().rev()walks the vector backwards. Its items are references to the elements, which here are themselves references, so each item has the type&&str.cloned()copies each item one level, turning&&strinto&str.collect::<Vec<&str>>()builds the reversed vector, andjoin(" ")glues its elements together with one space between them, returning a newString, which is the return type.
Tracing "sky is blue": words is ["sky", "is", "blue"], the reversed vector is ["blue", "is", "sky"], and joining gives "blue is sky".
The solution in Rust
impl Solution {
fn reverse_words(input: String) -> String {
let words: Vec<&str> = input.split_whitespace().collect();
words.iter().rev().cloned().collect::<Vec<&str>>().join(" ")
}
}
Rust details worth knowing:
- Borrowed words. The elements of
wordsare slices ofinput, soinputmust stay alive whilewordsis in use. Inside the function this is automatic. - Why
cloned(). Cloning a&strcopies only the pointer and length, not the text. Without it,collectwould give aVec<&&str>. Callingjoinon aVec<&&str>doesn't compile, socloned()is what makes the join work. - The turbofish.
collect::<Vec<&str>>()names the target type inline. It is needed here because the result is used straight away as the receiver of.join(" "), with no variable to carry an annotation. - Shorter alternative. The extra vector can be dropped:
input.split_whitespace().rev().collect::<Vec<&str>>().join(" ")does the same, because the word iterator can also run backwards. - No semicolon. The last expression is the return value.
Complexity
Time: O(n). Splitting scans the text once, reversing visits each word once, and joining copies each character once, where n is the length of the string.
Space: O(n). The vector of word slices holds up to one entry per word, and the result is a new string as long as the input.
Edge cases and common mistakes
- One word.
"one"comes back as"one". - Empty string.
split_whitespace()finds no words, the vector is empty, and the joined result is"". - Extra spaces. The statement promises single spaces between words. If the input had more, the function would still return single spaces:
" a b "gives"b a", becausesplit_whitespace()skips runs of spaces and ignores spaces at the ends. Splitting on' 'withsplit(' ')behaves differently, since"a b".split(' ')includes an empty piece between the two spaces. - Other whitespace.
split_whitespace()treats tabs and newlines as separators too, so"a\tb"is two words. - Reversing the characters. Reversing the whole string gives
"eulb si yks", which reverses each word as well. Only the order of the words should change. - Joining with an empty separator.
join("")would glue the words together as"blueissky".
Testing
"sky is blue"gives"blue is sky"."one"gives"one"."a b c d"gives"d c b a".""gives"".
