Reverse the ordering of words in a string

Question

I have this string s1 = "My name is X Y Z" and I want to reverse the order of the words so that s1 = "Z Y X is name My".

I can do it using an additional array. I thought hard but is it possible to do it inplace (without using additional data structures) and with the time complexity being O(n)?

Answer 1

Here is a C implementation that is doing the word reversing inlace, and it has O(n) complexity.

char* reverse(char *str, char wordend=0)
{
    char c;
    size_t len = 0;
    if (wordend==0) {
        len = strlen(str);
    }
    else {
        for(size_t i=0;str[i]!=wordend && str[i]!=0;i++)
            len = i+1;
    }
            for(size_t i=0;i<len/2;i++) {
                c = str[i];
                str[i] = str[len-i-1];
                str[len-i-1] = c;
            }
    return str;
}

char* inplace_reverse_words(char *w)
{
    reverse(w); // reverse all letters first
    bool is_word_start = (w[0]!=0x20);

    for(size_t i=0;i<strlen(w);i++){
        if(w[i]!=0x20 && is_word_start) {
            reverse(&w[i], 0x20); // reverse one word only
            is_word_start = false;
        }
        if (!is_word_start && w[i]==0x20) // found new word
            is_word_start = true;
    }
    return w;
}

Answer 2

In c, this is how you might do it, O(N) and only using O(1) data structures (i.e. a char).

#include<stdio.h>
#include<stdlib.h>
main(){
  char* a = malloc(1000);
  fscanf(stdin, "%[^\0\n]", a);
  int x = 0, y;
  while(a[x]!='\0')
  {
    if (a[x]==' ' || a[x]=='\n')
    {
      x++;
    }
    else
    {
      y=x;
      while(a[y]!='\0' && a[y]!=' ' && a[y]!='\n')
      { 
        y++;
      }
      int z=y;
      while(x<y)
      {
        y--;
        char c=a[x];a[x]=a[y];a[y]=c; 
        x++;
      }
      x=z;
    }
  }

  fprintf(stdout,a);
  return 0;
}

Answer 3

This is not perfect but it works for me right now. I don't know if it has O(n) running time btw (still studying it ^^) but it uses one additional array to fulfill the task.

It is probably not the best answer to your problem because i use a dest string to save the reversed version instead of replacing each words in the source string. The problem is that i use a local stack variable named buf to copy all the words in and i can not copy but into the source string as this would lead to a crash if the source string is const char * type.

But it was my first attempt to write s.th. like this :) Ok enough blablub. here is code:

#include <iostream>
using namespace std;

void reverse(char *des, char * const s);
int main (int argc, const char * argv[])
{    
    char* s = (char*)"reservered. rights All Saints. The 2011 (c) Copyright 11/10/11 on Pfundstein Markus by Created";
    char *x = (char*)"Dogfish! White-spotted Shark, Bullhead";

    printf("Before: |%s|\n", x);
    printf("Before: |%s|\n", s);

    char *d = (char*)malloc((strlen(s)+1)*sizeof(char));  
    char *i = (char*)malloc((strlen(x)+1)*sizeof(char));

    reverse(d,s);
    reverse(i,x);

    printf("After: |%s|\n", i);
    printf("After: |%s|\n", d);

    free (i);
    free (d);

    return 0;
}

void reverse(char *dest, char *const s) {
    // create a temporary pointer
    if (strlen(s)==0) return;
    unsigned long offset = strlen(s)+1;

    char *buf = (char*)malloc((offset)*sizeof(char));
    memset(buf, 0, offset);

    char *p;
    // iterate from end to begin and count how much words we have
    for (unsigned long i = offset; i != 0; i--) {
        p = s+i;
        // if we discover a whitespace we know that we have a whole word
        if (*p == ' ' || *p == '\0') {
            // we increment the counter
            if (*p != '\0') {
                // we write the word into the buffer
                ++p;
                int d = (int)(strlen(p)-strlen(buf));
                strncat(buf, p, d);
                strcat(buf, " ");
            }
        }
    }

    // copy the last word
    p -= 1;
    int d = (int)(strlen(p)-strlen(buf));
    strncat(buf, p, d);
    strcat(buf, "\0");

    // copy stuff to destination string
    for (int i = 0; i < offset; ++i) {
        *(dest+i)=*(buf+i);
    }

    free(buf);
}

Answer 4

Printing words in reverse order of a given statement using C#:

    void ReverseWords(string str)
    {
        int j = 0;
        for (int i = (str.Length - 1); i >= 0; i--)
        {
            if (str[i] == ' ' || i == 0)
            {
                j = i == 0 ? i : i + 1;

                while (j < str.Length && str[j] != ' ')
                    Console.Write(str[j++]);
                Console.Write(' ');
            }
        }
    }

Answer 5

This quick program works..not checks the corner cases though.

#include <stdio.h>
#include <stdlib.h>
struct node
{
    char word[50];
    struct node *next;
};
struct stack
{
    struct node *top;
};
void print (struct stack *stk);
void func (struct stack **stk, char *str);
main()
{
    struct stack *stk = NULL;
    char string[500] = "the sun is yellow and the sky is blue";
    printf("\n%s\n", string);
    func (&stk, string);
    print (stk);
}
void func (struct stack **stk, char *str)
{
    char *p1 = str;
    struct node *new = NULL, *list = NULL;
    int i, j;
    if (*stk == NULL)
    {
        *stk = (struct stack*)malloc(sizeof(struct stack));
        if (*stk == NULL)
            printf("\n####### stack is not allocated #####\n");
        (*stk)->top = NULL;
    }
    i = 0;
    while (*(p1+i) != '\0')
    {
        if (*(p1+i) != ' ')
        {
            new = (struct node*)malloc(sizeof(struct node));
            if (new == NULL)
                printf("\n####### new is not allocated #####\n");
            j = 0;
            while (*(p1+i) != ' ' && *(p1+i) != '\0')
            {
                new->word[j] = *(p1 + i);
                i++;
                j++;
            }
            new->word[j++] = ' ';
            new->word[j] = '\0';
            new->next = (*stk)->top;
            (*stk)->top = new;
        }
        i++;
   }
}
void print (struct stack *stk)
{
    struct node *tmp = stk->top;
    int i;
    while (tmp != NULL)
    {
        i = 0;
        while (tmp->word[i] != '\0')
        {
            printf ("%c" , tmp->word[i]);
            i++;
        }
        tmp = tmp->next;
    }
    printf("\n");
}

Answer 6

Store Each word as a string in array then print from end

public void rev2() {
    String str = "my name is ABCD";
    String A[] = str.split(" ");

    for (int i = A.length - 1; i >= 0; i--) {
        if (i != 0) {
            System.out.print(A[i] + " ");
        } else {
            System.out.print(A[i]);
        }
    }

}