CareerCup

I presume you mean unique rotations? So if String is "OOO", only print a single "OOO"?

We can use a trie to keep track in that case (not sure if you disallow that).


Follow up is a classic: Append Str1 to itself and check if Str2 is a substring ( using KMP, Boyer-Moore etc) and of the appropriate length.

Here is a sample code.But it will print all three rotation for the input "ooo".

package com.test;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class AllRotation {

	public static void main(String[] args) throws IOException {
		BufferedReader obj = new BufferedReader(new InputStreamReader(System.in));
		System.out.println("Enter the String whose Rotation is to be found");
		String input = obj.readLine();
		System.out.println("Enter the String to check whether it's rotation of first String");
		String input2 = obj.readLine();
		boolean isRotated = false;
		for (int index = 0; index < input.length(); index++) {
			String rotatedString = input.substring(index)+ input.substring(0, index);
			System.out.println(rotatedString);
			if (rotatedString.equals(input2)) {
				isRotated = true;
			}
		}
		System.out.println("The Second input is Rotation of first " + isRotated);
	}

}

void print_all_rotations(char* pstr)
{
	int n = strlen(pstr);
	char *temp =(char*) malloc(1 + 2*n);
	memcpy(temp, pstr, sizeof(char)*n);
	memcpy(temp+n, pstr, sizeof(char)*n);

	
	for (int i = 1; i <= n; i++)
	{
		char save = *(temp + i + n);
		*(temp + i + n) = '\0';
		printf("%s\n", temp + i);
		*(temp + i + n) = save;
	}
	delete[] temp;
}

For the second question u can use this: Given A and B you can find if B is a rotation of A.
Put A = A + A.
Then B is a rotation of A iff B is a substring of A.

public boolean isRotation(String a,String b)
{
String c=b+b;
int trueOrFalse=c.indexOf(a);
if (trueOrFalse == -1) return false;
else return true;
}

static List<string> find_rotations(string original)
        {
            List<string> tempList = new List<string>();

            for(int i = 0; i < original.Length; ++i)
            {
                char[] tempChars = original.ToCharArray();

                for(int j = 0; j < original.Length; ++j)
                {
                    tempChars[j] = original[(i + j) % original.Length];
                }

                tempList.Add(new string(tempChars));
            }

            return tempList;
        }

        static bool is_rotation(string string1, string string2)
        {
            if (string1.Length != string2.Length)
                return false;

            if (find_rotations(string1).Contains(string2))
                return true;

            return false;
        }

Here is the solution I have implemented in the interview, from scratch, given the above conditions...

static void Main(string[] args)
        {
            Program pg = new Program();
            string str1 = "TIME";
            string str2 = "ETIM";
            bool is_rotate = false;
            is_rotate = pg.is_rotation(str1, str2);
            if(is_rotate==true)
                Console.WriteLine("Str2 is a rotation of Str1");
            else
                Console.WriteLine("Str2 is not a rotation of Str1");
        }

        public bool is_rotation(string str1, string str2)
        {
            string[] sarr = new string[str1.Length];
            bool is_rotation = false;
            sarr = rotate_str(str1);

            for (int k = 0; k < sarr.Length; k++)
            {
                Console.WriteLine(sarr[k]);
            }


            int i = 0;
            for (i = 0; i < str1.Length;i++)
            {
                if(sarr[i] == str2)
                {
                    is_rotation = true;
                    return is_rotation;
                }
            }

                return is_rotation;
        }

        public string[] rotate_str(string str)
        {
            char[] ca = str.ToCharArray();
            int j = 0, len = ca.Length - 1, k = 0, m=0;
            char temp=' ';
            string[] sa = new string[str.Length];
            for (k = 0; k < str.Length; k++)
            {
                temp = ca[m];                
                for(j=0; j<len; j++)
                {                    
                    ca[j] = ca[j + 1];
                }
                ca[j] = temp;
                sa[k] = new string(ca);
                if(k==sa.Length-1)
                {
                    return sa;
                }
                else
                {
                    ca = sa[k].ToCharArray();
                    continue;

                }
            }

            return sa;

}

Solution for second problem: concatenate the string with itself and search for the given string in the concatenated string.

def find(string, l_s):
        if l_s in string:
                return 1
        else:
                return 0

def main(string, l_s):
        t_string = string + string
        check = find(t_string, l_s)
        print check

if __name__ == "__main__":
        main(sys.argv[1], sys.argv[2])

Solution for first problem:
consider array of size 5 , and i want to shift each element n times then:
(5+n+ i) %5 where i is the actual position of a value in the array. This equation will give the new location to the array.

def rotate(string, shift):
        i = 0
        if shift == len(string):
                return
        for i in range(0, len(string)):
                print string[(len(string)+shift+i)%len(string)]
        rotate(string, shift+1)
def main(string, l_s):
        rotate(string, 0)

if __name__ == "__main__":
        main(sys.argv[1])

void allRotationOfString(string str) {
    if (str.size() == 0) {
        cout<<endl<<"Invalid input for allRotationOfString";
        return;
    }
    cout<<endl;
    for (int i=0; i<str.size(); i++) {
        str = str.substr(1, str.size()) + str[0];
        cout<<str<<" ";
    }
}

bool includedInAllRotationOfString(string str1, string str2) {
    if (str1.size() == 0) {
        return false;
    }
    for (int i=0; i<str1.size(); i++) {
        str1 = str1.substr(1, str1.size()) + str1[0];
        if (str1 == str2)
            return true;
    }
    return false;
}

#include <stdio.h>

#define True 1
#define False 0

unsigned char compare_string_length(unsigned char *, unsigned char*);

unsigned char compare_strings(unsigned char *, unsigned char*, unsigned char);

int main()
{
    unsigned char Str1[10], Str2[10];
    unsigned char i=0, Result=False, String_count= False;
    
    printf("Input String 1\n");
    fgets(Str1, sizeof(Str1), stdin);
    printf("Input String 2\n");
    fgets(Str2, sizeof(Str2), stdin);
    
    String_count = compare_string_length(Str1, Str2);
  
    if(String_count == False)
    {
        printf("Strings length not same\n");
    }
    
    else
    {
        Result = compare_strings(Str1, Str2,String_count);
        
        if(Result == False)
        {
           printf("Strings is not a rotation\n");
        }
        
        else
        {
          printf("Strings is a rotation\n");
        }
    }


    return 0;
}

unsigned char compare_string_length(unsigned char *Str_El_Com1, unsigned char*Str_El_Com2)
{
    unsigned char Temp1=0, Temp2=0, Com_Return;
    
    while(Str_El_Com1[Temp1]!='\n')
    {
        Temp1++;
    }
    
    while(Str_El_Com2[Temp2]!='\n')
    {
        Temp2++;
    }
    
    if(Temp1 !=Temp2)
    {
        Com_Return = 0;
    }
    
    else
    {
        Com_Return = Temp1;
    }
	
    return Com_Return;
    
}


unsigned char compare_strings(unsigned char *Str_Com1, unsigned char*Str_Com2, unsigned char compare_count)
{
    unsigned char Temp1=0, Temp2=0, Com_Return, Failure = False, match_found = 0, match_found_flag=0;
    


	while((Str_Com1[Temp1]!='\n' ) && Failure == False)
    {
	 
	  while(Str_Com2[Temp2]!='\n')
	  {
		 if(Str_Com1[Temp1] == Str_Com2[Temp2])
		  {
			//Some dummy character 
			Str_Com2[Temp2] = '#';
			match_found++;
			match_found_flag = 1;
			Temp2=0;
			break;
		  } 
	
		Temp2++; 
	  }
	  	  
	  if(match_found_flag == 0)
	  {
		Failure = True; 
	  }
	  
      Temp1++;
	  
	 
    }
    
    if(match_found == compare_count)
    {
        Com_Return = True;
    }
    
    else
    {
        Com_Return = False;
    }
    return Com_Return;

}

str1='top'
for i in range(len(str1)):
    print(str1[i:]+str1[:i])

int checkRotation(char *str1, char *str2) // checks if str2 is a rotation of str1
{
  int i, j, k;
  int len = strlen(str1);
  
  if(strlen(str2) != len)
    return 0;
	
  for(j=0; j<len; j++) // This loop is to take care of multiple occurrence of first character of str1 in str2
  {	
    while(j<len && str2[j++] != *str1); // find the occurrence of the first letter of str1 in str2
    if(j == len) // first char is not there in the second string or no match found in subsequent loops also.
      return 0;
    
    for(i=0, k=j-1; i<len; i++)
    {
      if(str1[i] != str2[k])
	    break;    
	  k = (k+1)%len;
    }
	if(i==len)
	  return 1;
  }  
  return 0;
}