Clicky

Mustafa Veysi Soyvural: Reverse Words of a String

Monday, 17 December 2007

Reverse Words of a String

Q.) How do you reverse the words in a string?

"My name is Amit Agarwal"
to
"Agarwal Amit is name My"

A O(n) and 'in space' solution is appreciable.

- First reverse the whole string
- Then reverse each word in the string

Test Cases:
- NULL string
- "" empty string
- "a" string that consists only one word
- "mustafa"
- "a b"
- "Mustafa Veysi Soyvural"
- "Mustafa Veysi Soyvural" more than one space between words

void reverse_words( char s[] ) {
char *p, temp;
int len = 0, i = 0, index = 0, word_len = 0;
if ( NULL == s ) return;
for ( p = s; *p != '\0'; p++ );
len = p - s;

/* reverse whole string */
for ( i = 0; i < (len / 2); i++ ) {
temp = s[ i ];
s[ i ] = s[ len - i - 1 ];
s[ len - i - 1 ] = temp;
}

/* reverse each word */
p = s;
while ( index < len ) {
if ( *p != ' ' && *p != '\0' ) p++;
else {
word_len = p - &s[ index ];
/* reverse word */
for ( i = 0; i < (word_len / 2 ); i++ ) {
temp = s[ i + index ];
s[ i + index ] = s[ index + word_len - i - 1 ];
s[ index + word_len - i - 1 ] = temp;
}
index += word_len + 1;
p++;
}
}
}

No comments: