CareerCup

Hey this can be done in various ways...the best approach is to maintain distinct char pointers to individual words in the sentence and then form new words for specified order by assigning the words pointed by those particular pointers in the new sentence.
For example, for sentence char *input = "i am an indian"; there can be 4 char pointers declared, say
char *p1,*p2,*p3,*p4;
then assign pointers such that they should point to individual words, i.e.
p1 = "i" , p2 = "am" , p3 = "an" , p4 = "indian"

and then declare new sentence as follow
char* new = (char *) malloc( (strlen(input)+1)*sizeof(char) );
Note: size is inputstring lenght + 1 to accomodate the null character at the end.

Now, start assigning individual words to this new *empty* string
pointed by char * output.

This is the algorithm..

Here is the code that I have tested with GCC..it work superb, complexity is O(2n)..


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


char * reverse(char *input)
{
char *tmp = input;
int count = 0;
while(tmp && *tmp)
{
if (*tmp == ' ') count++;
tmp++;
}
char *p[++count];
char *new = (char *) malloc((strlen(input)+1)*sizeof(char));
char *output = new;
p[0] = input;
int i=1;
while(input && *input && i<count)
{
if (*input == ' ')
{
p[i++] = ++input;
}
else
{
input++;
}
}
int j;
for(j=count-1;j>=0;j--)
{
while(*p[j] != '\0' && *p[j] != ' ' )
{
*new++ = *p[j]++;
}
*new++ = (j > 0)? ' ':'\0';
}
return output;
}


int main()
{
char y[] = "I am an Indian";
printf("%s\n",y);
char *x = reverse(&y[0]);
while(x && *x)
{
printf("%c",*x);
x++;
}
return 0;
}

assume S is the string array of words....size of S is n.

for i = n-1..1
S = reverse(reverse(S[0]) reverse(S[1..i]))
print S

ROtate array {0,1,2,3}. 0 index of first word, 1 index of second word etc..
Function(int[] array, int rotateindex)

I will call this function for all the rotateindex i.e. 0 to 4 and based on the final rotated array. i will outpout the word at the indexex to the console.

Hi,
For in place reversal,
1. Reverse complete sentence
2. Reverse each word individually

time complexity O(n)
space O(1)

Depends on how the string is presented, as an array of characters or as a linkedlist of words..
My best bet would be to convert the given thing into a linked list of words, and then manipulate the string accordingly using 2 pointers, one at the end, i.e. at the word 'indian' and one at the starting of the sentence..

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

void reverse(char *str)
{
int ii;
char temp;
int len = strlen(str) - 1;
for(ii = 0; ii < len; ii++, len--)
{
temp = str[ii];
str[ii] = str[len];
str[len] = temp;
}
}

int main(int argc, char *argv[])
{
char str[] = "Hi a this is Lakshman";
int len = strlen(str);
reverse(str);

char *token = NULL;
for(token = strtok(str, " "); token != NULL; token = strtok(NULL, " "))
reverse(token);
int ii;
for(ii = 0; ii != len; ii++)
{
if(str[ii] == '\0')
str[ii] = ' ';
}

printf("%s\n", str);
return 0;
}

package demo;

import java.util.Scanner;

public class JavaDemoTwo {
	private static String original = "";
	public JavaDemoTwo() {
		// TODO Auto-generated constructor stub
	}
	
	static void readInput(){
	    Scanner in = new Scanner(System.in);	 
	    System.out.print("Enter a string to reverse : ");
	    original = in.nextLine();
	    in.close();
	}
	
	static void reverseString(){ 
		String reverse = "";
	    int length = original.length();	 
	    for ( int i = length - 1 ; i >= 0 ; i-- )
	         reverse = reverse + original.charAt(i);	 
	    System.out.println("Reverse of entered string is: "+reverse);
	    
	}
	
	static String rearrangeStrings(String myString){
		int indexOfSpace = myString.indexOf(" ");
		String finalString = myString.substring(indexOfSpace  + 1)+" "+myString.substring(0, indexOfSpace);
		original = finalString;
		return original;
	  
	}

	
	public static void main(String[] args) {
		readInput();
		System.out.println("input string : " + original);
		reverseString();
		for(int i=0;i<original.split(" ").length-1;i++ )
			System.out.println(rearrangeStrings(original));

	}

}

Algo:
split the input string on space delimiter.
for fisrt output push fisrt string in stack & then print remaining strings & then pop the stack.
for 2nd output push 2 strings in stack & print remaining & then pop both the string from stack & like wise for the 3rd output ,push 3string in stack & print remaining & then pop the stack with all three strings.

Here goes the java code:
public class Stoken{
public static void main(String[] args) {
String a = "I am an indian";
Stack<String> stack = new Stack<String>();
String[] temp;
String delimiter = " ";
// given string will be split by the argument delimiter provided.
temp = a.split(delimiter);
for(int i=0;i<temp.length-1;i++){
int k=i;

for(int l = 0;l<=k;l++){
stack.push(temp[l]);

}

for(int j=i+1;j<temp.length;j++){
System.out.print(temp[j]+" ");
}
while(!stack.isEmpty()){
System.out.print(stack.pop()+" ");
}
System.out.println();
}


}




}

Here is a clean C++ solution. Tested with VS.

#include <iostream>

using namespace std;

int cnt;

void SortWord(char str[], int len)
{
	char *temp = new char[len];
	memset(temp, 0, len);

	for (int i = 0; str[i] != '\0' && cnt > i; i++)
	{
		if (str[i] == ' ') {
			memcpy(temp, &str[i + 1], len - i - 1);

			str[i] = '\0';
			temp[len - i - 1] = ' ';
			
			memcpy(&temp[len - i], str, i);
			temp[len] = '\0';

			memcpy(str, temp, len);

			cout << str << endl;

			cnt = cnt - i - 1;
			SortWord(str, len - i - 1);

			break;
		}
	}
}

int main()
{
	char input[] = "this is a test";
	int len = strlen(input);
	cnt = len;

	SortWord(input, len);

	return 0;
}

Why not use a circular queue.