CareerCup

Separate each word and put them into stack and call popup.

reverse (in place) each word > I ma maS
reverse whole sentence > Sam am I

Say given string is: "My name is Anurag Singh"
1. reverse given string: "hgniS garunA si eman yM"
2. Now reverse each word: "Singh Anurag is name My"


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

void reverseString(char *s,int start, int end);
int main(int argc, char *argv[])
{
char *s="My name is Anurag Singh";
printf("%s\n",s);
int len=strlen(s);
reverseString(s,0,len-1);
printf("reverse by charater: %s\n",s);

int i=0,start=0;
while(i<=len)
{
if(s[i] && s[i] != ' ')
i++;
else
{
reverseString(s,start,i-1);
start=++i;
}
}
printf("Reverse by Word: %s\n",s);
return 0;
}

void reverseString(char *s,int start, int end)
{
int i=0,j=0;
char c;
for(i=start,j=end;i<j;i++,j--)
{
c=s[i];
s[i]=s[j];
s[j]=c;
}
}

I implement it with java:


public static String revers(String s)
{
String out = "";
int i=0;
for(int j=0; j<s.length();j++){
if(s.charAt(j)==' '){

out = s.substring(i,j)+" "+out;
i=j;
}
}

if(s.charAt(s.length()-1)!=' ')
out = s.substring(i)+out;

return out;
}

use a stack, push each word into it and then pop out.

We can swap the string without using temporary variables..

void reverseString(char *inString,int start, int end)
{
int i=0,j=0;
for(i=start,j=end;i<j;i++,j--)
{
inString[i] ^= inString[j];
inString[j] ^= inString[i];
inString[i] ^= inString[j];
}
}

We can split the string into tokens and reverse append, like below:
public class StringReverse {

public static void main(String[] args) {
String testStr = "Java is platform neutral language";
System.out.println("input=" + testStr);
System.out.println("output=" + reverseString(testStr));
}

public static String reverseString(String s) {
if (s != null && s.trim().length() != 0) {
String[] tokens = s.split("\\s");
System.out.println("tokens=" + Arrays.asList(tokens));
StringBuffer sb = new StringBuffer();
for (int i=tokens.length-1; i>=0; i--) {
sb.append(tokens[i]).append(' ');
}
return sb.toString();
} else {
return null;
}
}
}

OUTPUT:
input=Java is platform neutral language
tokens=[Java, is, platform, neutral, language]
output=language neutral platform is Java

using regular expression is the best choice if allowed, no matter what kind of empty symbols(\t, \n, \r) between words.

String reverseString(String s){
Pattern p = Pattern.compile("\\w+");
Matcher m = p.matcher(s);
String reverse = null;
while(m.find())
if(reverse == null) reverse = m.group();
else reverse = m.group()+" "+reverse;
return reverse;
}

use a variable for s.length() in for loop.it increases the complexity of the solution.

char * s="blah blah bhah" would have the string in the read only section and *q would be a reference to it.u can access it but u cant modify it.

if u use char s[]="hello how r u" , the string would be located in your code section and it can be read/modify.

@arasu,

if inString[i] == inString[j]

urs will not work

//Reverese a string: (courtesy: crack the interview)
	void Reverse(char *str, int start, int end)
	{
		if(start >= end) return;
		else
		{
			char temp = *(str+start);
			*(str+start) = *(str+end);
			*(str+end) = temp
			
			Reverse(str,++start,--end); 
		}
	}
	
//Reverese a words in the sentence:
	void WordReverese_Sentence(char *str)
	{
		int len = strlen(str);
		
		if(len == 0 || len == 1) return;
		int i = 0, j =0;
		
		//precondition	: i is always = j
		//Logic			: 	in the loop j will first find the end of the current word
							Then, it will find the next possible spot for i
		while(j<len)
		{
			while(j<len && str[j] != 32)
			{
				j++;
			}
			
			if((j-1) < len) Reverse(str,i,j-1);
			
			while(j<len && str[j] == 32)
			{
				j++;
			}
			
			if(j<len) i=j;		
		}
		
	}

Works well for
1. empty string
2. one character
3. one word
4. multiple words seperated by single spaces
5. multiple words seperated by multiple spaces

Here is solution based on python. c++ code should be similarly short using STL copy function for splitting the string.

def reverse(s):
if len(s)==0:
return
t = s[1:]
sc= s[0]
reverse(t)
print sc, " ",

void ReverseWordsInString(char *str)
{
	int l = 0;

	if(!str)
	{
		printf("NULL String");
		return;
	}

	l = strlen(str);// O(N)

	int s = 0; 	//Starting index of string
	inr e = l-1;	//End index of string
	char t_ch;

	//I: the bus
	while(s<e) //Reverse String // O(N)
	{
		//Swap Sring charcter
		t_ch = *(str + s);
		*(str + s) = *(str + e);
		*(str + e) = t_ch;
		s++;
		e--;
	}
	//O: sub eht
	// bus the

	//Reverse words of string
	int space = 1;
	int i = 0;
	s = 0; e = 0;
	int t_s, t_e;
	
	for(i=0; i<l; i++) // O(N)
	{
		if(str[i] == ' ')//Check for while space
		{
			if(!space)//Check for eleminating multiple spaces
			{
				e = i-1;
				t_s = s;
				t_e = e;
				while(t_s<t_e)//reverse word
				{
					t_ch = *(str + s_t);
					*(str + s_t) = *(str + e_t);
					*(str + e_t) = t_ch;
					t_s++;
					t_e--;
				}
				space = 1;
			}
			s = i+1;
		}
		else
		{
			space = 0;
		}
	}
	printf("String after word reverse: %s", str);
	return;
}

#define MAX_LEN 256

char *word_reverse(char *str) {
int i = 0;
char *p;
p = (char *)malloc(sizeof(char) * MAX_LEN);
while(*str != ' ' || *str != '\0') {
p[i++] = *str;
str++;
}
if (*str == ' ') {
str++;
str = word_reverse(str);
strcat(str, p);
strcpy(p, "");
strcpy(p, str);
}
return p;
}

It can also be done using array of strings...

void reverse_by_words(char *src)
{

	char *dest,*ptr, **reverse;
	int len=0;
	dest=malloc(sizeof(char)*strlen(src));
	strcpy(dest,src);
	ptr=strtok(dest, " ");
	
	while (ptr != NULL) {
	
		reverse[len]=malloc(strlen(ptr)*sizeof(char));
		strncpy(reverse[len],ptr,strlen(ptr));
		ptr	= strtok(NULL, " ");
		len++;
	}
	
	while (len--!=0) {
		printf("%s ",reverse[len]);
		
	}
	printf("\n");
	

}

Use two stacks, A and B. Push in A till space is encountered. Then push in B till next space is encountered..pop from B and push in A till B is empty..continue the loop till all words are pushed..then just pop A till empty (apply suitable error checks)

first reverse each word, then reverse the whole string
I am a guy
I ma a yug
Now just reverse it
guy a am I
time O(N), space O(1)

static string ReverseString(char[] str)
{
Reverse(str, 0, str.Length - 1);

//reverse each word
int startWord = 0;
for (int i = 0; i < str.Length; i++)
{
if (str.Contains(' '))
{
if (str[i] == ' ' || str[i] == '\0')
{
Reverse(str, startWord, i - 1);
startWord = i + 1;
}
else if ((i + 1) == str.Length)
{
Reverse(str, startWord, i);
}
}
else
break;
}
Console.WriteLine(str);
return str.ToString();
}

static void Reverse(char[] str, int beginindex, int endindex)
{

while (beginindex < endindex)
{
char temp = str[beginindex];
str[beginindex] = str[endindex];
str[endindex] = temp;

beginindex++;
endindex--;
}

}

<pre lang="" line="1" title="CodeMonkey20762" class="run-this">void ReverseString(char* str)
{
int i = strlen(str) - 1;
int spaces1 = 0;
char* new_string = (char*)malloc(strlen(str)*sizeof(char));
while(i >= 0)
{
spaces1 = i;
while(str[i] != ' ')
{
i--;
if(i == 0)
{
break;
}
}
if(i != 0)
{
memcpy((char*)new_string + strlen(str) - spaces1 - 1, (char*)str + i + 1, spaces1 - i);
new_string[strlen(str) - i - 1] = ' ';
}
else
{
memcpy((char*)new_string + strlen(str) - spaces1 - 1, (char*)str + i, spaces1 - i + 1);
memset((char*)new_string + strlen(str), NULL, 1);
}
i--;
}
}

</pre><pre title="CodeMonkey20762" input="yes">
</pre>

#include <stdio.h>
#include <conio.h>
void main()
{
char str [] = "I am good boy";

char *ptr1 , *ptr2 ,*start;
ptr1=str;
while (*ptr1!='\0'){
ptr1++;
}
start=str;
while(start<=ptr1){
if(*ptr1==' ')
{
*ptr1 = '\0';
ptr1++;
ptr2=ptr1;
printf("%s",ptr2);
printf(" ");
}
if(ptr1 == start){
printf("%s",start);}
ptr1--;
}
getch();
}

Try this code!!

public String reversebywords(String str){

String[] words = str.trim().split("\\s+");
StringBuilder sb = new StringBuilder("");
int i = (words.length)-1;

while(i>=0){
sb = sb.append(words[i]).append(" ");
i--;
}
return sb.toString().trim();
}