Reverse Words in a String
Split away the blanks, then swap from both ends inward
Two problems are hiding in one here, and mixing them is what makes this question fiddly. The first is spacing: a raw split on a space leaves an empty token wherever spaces were doubled, or at the very start and end of the string. Throw those away and the messy input becomes a clean list of words. The second is the reversal itself, which is now the ordinary two-pointer swap: one pointer at each end, trade the two words, step inward. Once the pointers meet, everything is already in place, and joining with a single space cannot reintroduce the spacing mess because the blanks were dropped before the reversal ever started.
Details
Animated on: s = " the sun is not up yet " — reverse the order of the words, collapsing every run of spaces down to one and dropping the leading and trailing ones.
Problem:Reverse Words in a StringMedium
Split away the blanks, then swap from both ends inward
step 1 / 10
Splitting " the sun is not up yet " on a single space gives 10 tokens, and 4 of them are empty — one for every leading, trailing or doubled space. Those blanks are not words.
1FUNCTION reverseWords(s):2 words <- EMPTY LIST3 FOR EACH token IN SPLIT(s, " "):4 IF token != "":5 APPEND token TO words6 l <- 07 r <- LENGTH(words) - 18 WHILE l < r:9 SWAP words[l] AND words[r]10 l <- l + 111 r <- r - 112 RETURN JOIN(words, " ")
← / → step · space play · Home restart
Every step in words
Show all 10 steps
- Splitting " the sun is not up yet " on a single space gives 10 tokens, and 4 of them are empty — one for every leading, trailing or doubled space. Those blanks are not words.
- Keeping only the non-empty tokens leaves 6 real words in their original order: the, sun, is, not, up, yet. The spacing problem is now solved and never has to be thought about again.
- l=0 holds "the" and r=5 holds "yet". In the reversed sentence the word at 0 has to end up at 5, so one swap puts BOTH of them where they belong.
- Swapped: "the" and "yet" traded places, so index 0 and index 5 are both final — that fixes 1 word at each end.
- l=1 holds "sun" and r=4 holds "up". In the reversed sentence the word at 1 has to end up at 4, so one swap puts BOTH of them where they belong.
- Swapped: "sun" and "up" traded places, so index 1 and index 4 are both final — that fixes 2 words at each end.
- l=2 holds "is" and r=3 holds "not". In the reversed sentence the word at 2 has to end up at 3, so one swap puts BOTH of them where they belong.
- Swapped: "is" and "not" traded places, so index 2 and index 3 are both final — that fixes 3 words at each end.
- l=3 is no longer left of r=2, so every pair has already been swapped — walking further would just undo the work. An even count means every word had a partner.
- Joining the 6 words with exactly one space each produces "yet up not is sun the" — no leading, trailing or doubled spaces survive, because they were never carried past the split.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.