There is going to be easier/faster ways. I am just giving a thought which should be good in learning purpose.
First, do whatever you have now, which reverse words, and leave those consecutive space untouched.
then write another method to do consecutive space removing.
have 2 pointer, start at the first position where it is not space.
A and B keep on moving on together.
if (A != B), then we do s[A] = s[B]; s[B] = ' ';
If s[A]
and s[A-1]
is space, then A stop (A is now at the 2nd space), and only B continue moving forward. By such way, A stay the same position and will continue to copy from B, until B gives a non-space character.
and it ends when B hit the end.
in psuedo code, it is something like
int a = first position of non-space;
int b = a;
while b < s.size() {
if (a != b) {
s[a] = s[b]
s[b] = ' '
}
if (both s[a] and s[a-1] are space) {
increment b;
// leave a untouched
} else {
increment a;
increment b;
}
}
Constant space, O(n) time
Another way, which can handle the removal of consecutive space in place when reversing words:
The hint is, include those extra spaces when doing reverse.
e.g. Given a string
abc def ghi
L (left)
first reverse is trivial so I am skipping it. The hint is, for second word, you are going to stop the L at the position right after the first space:
cba def ghi
L
the "right" side of the reverse is going to be the first right boundary of word:
cba def ghi
L R
Then do the reverse in place
cba fed ghi
L R
Then keep on finding the next position of L to start reverse again:
cba fed ghi
L
Take similar logic
cba fed ghi
L R
then
cba fed ihg
L R