Problem overview
The function reverse_words takes a String called input and returns its words in the opposite order. A word is a run of non-space characters, and words are separated by one space. For "sky is blue" the answer is "blue is sky".
Approach: two reversals
A natural idea is to split the string into words, reverse the list and join it again. This lesson uses a different trick that works directly on the characters, with only two kinds of reversal:
- Reverse the whole string.
"sky is blue"becomes"eulb si yks". The words are now in the right order, but each one is spelled backwards. - Reverse each word on its own.
"eulb"becomes"blue","si"becomes"is"and"yks"becomes"sky".
Both steps use one helper, reverse_range, which reverses a part of the vector in place with two pointers that swap and move toward each other. The only real work in the main function is finding where each word starts and ends: after the whole-string reversal, an outer loop walks to the start of a word, and an inner loop scans forward to the next space.
Step by step
- Collect the characters. A Rust string can't be indexed or edited by character, so
input.chars().collect()builds a mutableVec<char>namedchars. The annotation tellscollectwhat to build. - Handle the empty string. Store the length in
n. If it is 0, returninputat once: the next step needsn - 1, and ausizecan't go below zero. - Reverse everything. Call
Solution::reverse_range(&mut chars, 0, n - 1). The helper reverses the inclusive range from index 0 to indexn - 1. - Track the word start in a mutable
i, beginning at 0. - Loop over words with
while i < n, one pass per word. - Find the end. Declare
jequal toi. It scans forward. - Scan. An inner loop runs while
j < nandchars[j]is not a space. The bound check comes first, sochars[j]is never read past the end. - Advance
jwithj += 1inside that loop. Rust has no++. - Fix the word. The word occupies indices
itoj - 1. Ifj > i(the word isn't empty), callreverse_rangeon that range. The condition also keepsj - 1from underflowing. - Skip the space with
i = j + 1, so the next pass starts at the next word. After the last word,jequalsn, soigoes pastnand the loop ends. - Return the string.
chars.iter().collect()is the final expression. It gathers the characters into aStringbecause that is the function's return type. - Write the helper above
reverse_words, with parameterschars: &mut Vec<char>,mut i: usizeandmut j: usize. Themutallows the loop to move the indices. - Loop while
i < j. - Swap
chars[i]andchars[j]with the vector'sswapmethod. - Move both indices inward:
i += 1andj -= 1.
The solution in Rust
impl Solution {
fn reverse_range(chars: &mut Vec<char>, mut i: usize, mut j: usize) {
while i < j {
chars.swap(i, j);
i += 1;
j -= 1;
}
}
fn reverse_words(input: String) -> String {
let mut chars: Vec<char> = input.chars().collect();
let n = chars.len();
if n == 0 {
return input;
}
Solution::reverse_range(&mut chars, 0, n - 1);
let mut i = 0;
while i < n {
let mut j = i;
while j < n && chars[j] != ' ' {
j += 1;
}
if j > i {
Solution::reverse_range(&mut chars, i, j - 1);
}
i = j + 1;
}
chars.iter().collect()
}
}
Rust details worth knowing:
&mut Vec<char>. Passing&mut charslends the vector to the helper for the duration of the call. The helper can change it, andcharsis usable again afterwards. The variable must be declaredlet mutfor this to compile.mutin a parameter list.mut i: usizelets the function change its own copy of the index. It doesn't make the caller's value change.- Why
j -= 1is safe. The loop only runs wheni < j, sojis at least 1 when the subtraction happens. iinfersusize.let mut i = 0;has no suffix, buti < nand passing it to the helper fix its type.- Collecting
&charinto aString.chars.iter()yields references to characters, andStringcan be built from those directly, so no.cloned()is needed. - Characters, not bytes. Working on
Vec<char>means accented letters stay intact inside words.
Complexity
Time: O(n). The whole-string reversal touches each character once. The word loop scans each character once, and reversing a word of length k costs about k/2 swaps, so all the word reversals together are linear. Collecting the characters and building the result are linear too.
Space: O(n). The Vec<char> and the output string each hold n characters (a char takes 4 bytes). The reversals themselves use no more memory than the vector.
Edge cases and common mistakes
- Empty string. The early return handles it. Without it,
n - 1wraps to a huge number in an optimized build (and panics in a debug build), and the helper then indexes out of range. - One word.
"hello"is reversed to"olleh", then the single word is reversed back, so the result is"hello". - Spaces are mirrored, not collapsed. The statement promises single spaces. If the input had extra ones, the whole-string reversal would still move them to mirrored positions, and no space would be removed:
"a b"gives"b a", and a leading space becomes a trailing one. - Skipping the second step. Reversing only the whole string gives
"eulb si yks". Each word has to be reversed again. - Reading before checking the bound. Writing the scan condition as
chars[j] != ' ' && j < nreadschars[n]at the end of the last word, and Rust panics. The bound check goes first. - The range end. The word ends at
j - 1, becausejstops on the space, or atn. Passingjwould pull the space, or a position out of range, into the reversal.
Testing
"sky is blue"gives"blue is sky"."one two three four"gives"four three two one"."a b"gives"b a"."hello"gives"hello".""gives"".
