Reverse Words in a String - C Solution

1. Introduction

This post explores a common string manipulation problem in C programming - reversing the order of words in a given string. This problem is a classic example of string parsing and manipulation, useful in many applications such as natural language processing and text editing tools.

Problem

Given a string s, the task is to reverse the order of the words in it. A word is defined as a sequence of non-space characters, and the words in s are separated by at least one space. The returned string should have the words in reverse order, concatenated by a single space, and should not include any leading or trailing spaces or multiple spaces between words.

2. Solution Steps

1. Trim leading and trailing spaces from the string.

2. Split the string into words.

3. Reverse the order of the words.

4. Join the words into a single string with one space between each word.

5. Return the resulting string.

3. Code Program

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

// Function to reverse words in a string
char* reverseWords(char* s) {
    int len = strlen(s);
    char* result = (char*)malloc(len + 1);
    int wordStart = -1;
    int j = 0;

    for (int i = len - 1; i >= 0; i--) {
        if (s[i] != ' ') {
            if (wordStart == -1) wordStart = i;
        } else {
            if (wordStart != -1) {
                if (j > 0) result[j++] = ' ';
                for (int k = wordStart; k >= i; k--) {
                    result[j++] = s[k];
                }
                wordStart = -1;
            }
        }
    }
    if (wordStart != -1) {
        if (j > 0) result[j++] = ' ';
        for (int k = wordStart; k >= 0; k--) {
            result[j++] = s[k];
        }
    }
    result[j] = '\0';
    return result;
}

// Main function to test the reverseWords function
int main() {
    char s1[] = "the sky is blue";
    char* r1 = reverseWords(s1);
    printf("Reversed: %s\n", r1);
    free(r1);

    char s2[] = "  hello world  ";
    char* r2 = reverseWords(s2);
    printf("Reversed: %s\n", r2);
    free(r2);

    char s3[] = "a good   example";
    char* r3 = reverseWords(s3);
    printf("Reversed: %s\n", r3);
    free(r3);

    return 0;
}

Output:

Reversed: blue is sky the
Reversed: world hello
Reversed: example good a

Explanation:

1. Allocate memory for the result string.

2. Iterate through the string in reverse, identifying words.

3. Copy the words into the result string in reverse order.

4. Ensure that only a single space is added between words.

5. Return the reversed string.

6. Free the allocated memory in the main function.

7. The main function tests the reverseWords function with three examples and prints the reversed strings.