CareerCup

You don't have to worry abt spaces. Just reverse the entire string.

public static void revString(char[] charArr, int start , int end){
		while(start < end){
			char tmp = charArr[start];
			charArr[start] = charArr[end];
			charArr[end] = tmp;
			start++;
			end--;
		}
	}

Why we need to care about the white space?

Here is an implementation on string reversal:

basicalgos.blogspot.com/2012/03/4.html

It is very simple to reverse the whole string. But if wang to reverse string and keep every word unchanged, need addition code.

#include <stddef.h>
#include <string.h>
#include <stdio.h>
#include <conio.h>
// Reverse characters within lpszStart .. lpszEnd.
void ReverseString(char* lpszStart, char* lpszEnd)
{
    if (lpszStart >= lpszEnd)
    {
        return;
    }

    char* l = lpszStart;
    char* r = lpszEnd;
    while (l < r)
    {
        char ch = *l;
        *l = *r;
        *r = ch;
        ++l;
        --r;
    }
}

// Reverse the whole sentence, but every word is not reversed.
void ReverseSentence(char* lpszSentence)
{
    if (lpszSentence == NULL)
    {
        return;
    }

    char* lpszStart = lpszSentence;
    char* lpszEnd = lpszSentence + strlen(lpszSentence) - 1; // Exclude the null terminator.
    ReverseString(lpszStart, lpszEnd);

    // Then search word and reverse every word.
    lpszStart = lpszSentence;
    lpszEnd = lpszSentence;
    while (true)
    {
        // Forward search blank character.
        while (*lpszEnd != ' ' && *lpszEnd != '\0')
        {
            ++lpszEnd;
        }

        // Now lpszEnd should point to a blank or null terminator.
        ReverseString(lpszStart, lpszEnd-1);

        if (*lpszEnd == '\0')
        {
            break;
        }
        else
        {
            lpszStart = ++lpszEnd;
        }
    }

    printf(lpszSentence);
}

void main()
{
    char sz[] = "hello world";
    ReverseSentence(sz);
    getch();
}

string rev(string s)
{

    string res = "";
    string cur = "";

    for(int i=s.size()-1;i>=0;i--)
    {
        if(!isspace(s[i]))
        {
            cur = cur + s[i];
        }
        else
        {
            res = res + s[i]; // inorder to push the space character to the result

            for(int j=cur.size()-1;j>=0;j--)
            {
                res = res + cur[j];            
            }
             
            cur = "";
        }
    }
}

#include<iostream>
#include<string.h>
using namespace std;

int find_end(char* arr,int start)
{
int i;
for(i=start; *(arr+i)!=' ' && *(arr+i)!= '\0' ;i++)
return i;
}
void reverse(char* arr,int start, int end)
{
while(start<end)
{
char temp;
temp=arr[start];
arr[start]=arr[end];
arr[end]=temp;
start++;
end--;
}
}


int main()
{
char arr[]="Abhishek Gupta";

int start,end;
for(start=0;*(start+arr)!='\0' && start<strlen(arr); )
{
end=find_end(arr,start);
if(start==end)
break;
reverse(arr,start,end-1);
start=end+1;
}
cout<<arr<<endl;
return 0;

}

or you could use the concept of stack..

O(n) solution is one parse:
1. set two int start and right be the index of first non-space char so that start==right and s[start]!=' '
2. for(;right< size of string s;right++) do 3
3. if s[right] is space then we reverse s[start...right-1] and set start=right+1

private static void ReverseString(char[] input)
        {
            if(input == null || input.Length < 2)
                return;

            var spaces = new Queue<int>();
            spaces.Enqueue(0);
            for (int i = 0; i < input.Length; i++)
            {
                if(input[i] == ' ')
                {
                    spaces.Enqueue(i-1);
                    spaces.Enqueue(i+1);
                }
            }
            spaces.Enqueue(input.Length - 1);

            while (spaces.Count > 0)
            {
                var left = spaces.Dequeue();
                var right = spaces.Dequeue();
                while (left < right)
                {
                    var temp = input[left];
                    input[left] = input[right];
                    input[right] = temp;
                    ++left;
                    --right;
                }
            }
        }

You could use split:

public static String reverseWords(String input){

String output = "";

String[] inputList = splitWords(input," ");

for(int i = inputList.length-1; i>=0; i--)
output = output + inputList[i] + " ";

return output;
}

and the implementation of Split:

public static String reverseWords(String input){

String output = "";

String[] inputList = splitWords(input," ");

for(int i = inputList.length-1; i>=0; i--)
output = output + inputList[i] + " ";

return output;
}

You could use split:

public static String reverseWords(String input){

String output = "";

String[] inputList = splitWords(input," ");

for(int i = inputList.length-1; i>=0; i--)
output = output + inputList[i] + " ";

return output;
}

and the implementation of Split:

public static String reverseWords(String input){

String output = "";

String[] inputList = splitWords(input," ");

for(int i = inputList.length-1; i>=0; i--)
output = output + inputList[i] + " ";

return output;
}

public void ReverseSentence(string input)
{
	if (string.IsNullOrEmpty(input))
		throw new Exception("String Empty");

	char[] cArray = input.ToCharArray();
	int i = 0;
	int j = 0;
	while (true)
	{
		while (j < cArray.Length && cArray[j] == ' ')
			j++;
		if (j == cArray.Length)
			break;
		i = j;
		while (j < cArray.Length && cArray[j] != ' ')
			j++;
		ReverseWord(i, j - 1, cArray);
                }
}

public void ReverseWord(int start, int end, char[] inputWord)
{
	char temp;
	while (start < end)
	{
		temp = inputWord[start];
		inputWord[start] = inputWord[end];
		inputWord[end] = temp;
		start++;
		end--;
	}
}

in-place version:

void word_reverse()
{
        string str = "    a Hello World!    another_word! ab c ";
        char[] array = str.ToCharArray();            
            int word_start = 0;
            int word_end = 0;
            for (word_end = 0; word_end < array.Length; word_end++)
            {
                if (str[word_end] == ' ')
                {
                    Reverse(ref array, word_start, word_end - 1);
                    word_start = word_end + 1;
                    continue;
                }
                else if (word_end == array.Length - 1 && array[word_end] != ' ')
                {
                    Reverse(ref array, word_start, word_end);
                    break;
                }
            }
}

void Reverse(ref char[] array, int start, int end)
        {
            while (end >= start)
            {
                char tmp = array[end];
                array[end] = array[start];
                array[start] = tmp;
                end--;
                start++;
            }
        }