CareerCup

s1="Password"
s2="ordPassw"
s=s2+s2 //ordPasswordPassw
s.isSubstring(s1) //if this is true then s1 can be obtained by rotating s2

Probably we are looking for something like this:

stackoverflow.com/questions/2553522/interview-question-check-if-one-string-is-a-rotation-of-other-string

pseudocode:

s2=s1+s2
return issubstr(s1,s2)

The key to solve this problem is that if s1 and s2 are rotations, we must be able to divide them into two parts, respectively, so that the prefix of s1 is the suffix of s2, while the suffix of s1 is the prefix of s2.

so my solution is:
First find out all prefix of s1 that is also suffix of s2.
Next, find out all prefix of s2 that is also prefix of s1.
Finally, check if any pair of prefixes adds up to the original message.

This approach can be implemented within O(n) time, which is asymptotically fastest.

my code:

void ComputeSignature(string &str, vector<int> &signature)
{
        signature.push_back(0);
        int matched = 0;
        for (int i = 1 ; i < str.size() ; i++)  {
                while (matched > 0 && str[i] != str[matched])   {
                        matched = signature[matched-1];
                }
                if (str[i] == str[matched])     {
                        matched++;
                }
                signature.push_back(matched);
        }
}

bool IsRotate(string str1, string str2)
{
        if (str1.size() != str2.size()) return false;
        if (str1 == str2)       return true;

        vector<int> signature1;
        ComputeSignature(str1, signature1);
        vector<int> signature2;
        ComputeSignature(str2, signature2);

        //compute the longest prefix of str1 that is suffix of str2
        int matched = 0;
        if (str1[0] == str2[0]) matched = 1;
        for (int i = 1 ; i < str1.size() ; i++) {
                while (matched > 0 && str1[matched] != str2[i])
                        matched = signature1[matched-1];
                if (str1[matched] == str2[i])
                        matched++;
        }
        vector<int> prefixstr1; //all possible prefix length of str1 that is the suffix of str2
        while (matched > 0)     {
                prefixstr1.push_back(matched);
                matched = signature1[matched-1];
        }

        //now compute the str2's longest prefix that is also suffix of str1
        matched = 0;
        if (str1[0] == str2[0]) matched = 1;
        for (int i = 1 ; i < str2.size() ; i++) {
                while (matched > 0 && str1[i] != str2[matched])
                        matched = signature2[matched-1];
                if (str1[i] == str2[matched])
                        matched++;
        }

        vector<int> prefixstr2; //all possible prefix length of str2 that is the suffix of str1
        while (matched > 0)     {
                prefixstr2.push_back(matched);
                matched = signature2[matched-1];
        }

        //iterater the two array to see if a pair of element can add up to str1.size()
        int idx1 = 0;
        int idx2 = prefixstr2.size()-1;
        while (idx1 < prefixstr1.size() && idx2 >= 0)   {
                if (prefixstr1[idx1] + prefixstr2[idx2] == str1.size()) {
                        return true;
                }
                else if (prefixstr1[idx1]+prefixstr2[idx2] > str1.size())
                        idx1++;
                else
                        idx2--;
        }
        return false;
}

find the position in str1 for the first letter in str2. and then traverse and compare.....

Nicest solution would be to check if
a) Length of both string is the same
b) If index(s2, s1+s1) >= 0

But as an interviewer, I would not expect every one to get hold of this trick, especially in interview conditions.

I would expect pople to figure out that it is not necessary to compare str1 against all possible rotations of str2, but to look for the occurance(s) of the first letter of str1 in str2, re-arrange it, and compare vs str1. I believe this would be sufficient for an interview.

Algorithm: put every character from the first string in a hash table, which has char as key and value - int which shows the number of times the char occurs.
Iterate through the second string and remove all matching characters from the hash table, if there is no match - the strings are not anagrams. If after the iterations there is some value in the table - then they are not anagrams otherwise they are.

import java.util.Hashtable;
import java.io.Console;

public class Anagrams {
    public static void main(String[] args) {

        System.out.println("Example \"The eyes\" and \"They see\"");

        String str1;
        String str2;

        Console console = System.console();
        str1 = console.readLine("Enter the first string: ");   
        str2 = console.readLine("Enter the second string: ");   

        if (isAnagrams(str1.toLowerCase(), str2.toLowerCase())) {
            System.out.println("Anagrams");
        } else
            System.out.println("Not anagrams");
    }

    private static boolean isAnagrams(String str1, String str2) {
        if(str1==null || str2==null) throw new NullPointerException("s1 or s2");
        
        Hashtable<Character, Integer> ht = new Hashtable<Character, Integer>();
     

        for (char c : str1.toCharArray()) {
            if(c==' ')
            {
                continue;
            }

            if (ht.containsKey(c))
                ht.put(c, ht.get(c) + 1);
            else
                ht.put(c, 1);
        }

        for (char c : str2.toCharArray()) {
            if(c==' ')
            {
                continue;
            }

            if(!ht.containsKey(c))
             return false;

            else {
                if (ht.get(c) > 1)
                    ht.put(c, ht.get(c) - 1);
                else
                    ht.remove(c);
            }
        }

        if (!ht.keys().hasMoreElements())
            return true;

        return false;
    }

}

Definitely a naive solution, but can't we compare one of them with all possible rotations of the other?

# include <stdio.h>
# include <string.h>
int main(void)
{

char input1[100] = "Physical";
char input2[100] = "calPhysi";
char temp[100];
char temp1;
int i,j,len1 = strlen(input1);
strcpy(temp,input1);
for(i = 1;i<len1;i++)
{
temp1 = temp[len1-1];
for(j = len1-1;j>0;j--)
{temp[j] = temp[j-1];}
temp[0] = temp1;
if (!strcmp(temp, input2))
printf("They are a rotation of each other!");
}

return 0;
}

int main()
{
    char *s1 = "ABCD", *s2 = "ABCDEF";

    (!strcmp ( s1, strrev(s2)) )?printf("Yes \r\n"):printf("No \r\n");

	return 0;
}

#include<iostream.h>
#include<conio.h>

int main()
{
    char str1[]="sswordPa";
    char str2[]="Passwrd";
    char str3[]="password";
    int flag,i,j;
    j=flag=i=0;
    
   
                        while(str1[i]!=str2[j])
                        {
                                               j++;
                                               if(str2[j]==NULL)
                                               {
                                                cout<<"not matching";
                                                getch();
                                                return 0;
                                                }
                        }
                        
                        while(str1[i]!=NULL)
                        {
                                            if(str2[j]==NULL)
                                                             j=0;
                                            if(str1[i]!=str2[j])
                                            {
                                                                 cout<<"not matching";
                                                                 getch();
                                                                 return 0;
                                            }
                                            i++;
                                            j++;
                        }
                        
   
 cout<<"matched";  
    getch();
    return 1;
}

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

int is_rotation(char *s1, int len_1, char *s2, int len_2) {
int i, j;
int flag = 0;
i = 0;
while(i < len_1) {
if(s1[i] == s2[0]) {
break;
}
i++;
}
if(i >= len_1) { // not find the first character of s2 in s1
return 0;
}
j = 0;
while(i < len_1 && j < len_2) {
if(s1[i] != s2[j]) {
flag = 0;
break;
}
i = (i + 1) % len_1;
j++;
}
if(j == len_2) {
flag = 1;
}
return flag;
}
void main() {
char s1[] = "password";
char s2[] = "asswordp";
if(is_rotation(s1, strlen(s1), s2, strlen(s2))) {
printf("yes\n");
} else {
printf("no\n");
}
getchar();
}

int isRotationFromIndex(char * str1, char* str2, int index)
   {
   	while(*str1)
   	{
  	   if (str2[index] == NULL)
  	   {
  	   	index = 0;
  	   }
  	   
  	   if (*str1 != str2[index++])
  	   {
  	   	return 0;
  	   }
  	   
  	   str1++;
   	}
   
   	return 1;
   }
   
   int isRotation(char* str1, char* str2)
   {
   	if (str1 == NULL || str2 == NULL) return 0;
   	
   	int str1_length = strlen(str1);
   	int index = 0;
   	
   	if (str1_length != strlen(str2)) return 0;
   	
   	for (index = 0; index < str1_length ; ++index)
   	{
   		if (isRotationFromIndex(str1,str2,index))
   		{
   		   return 1;
   		}
   	}
   	
   	return 0;
   }

public class Permutation {


public static void main(String[] args) {

String permutation1 = "passprd";
String permutation2 = "sprdpas";

System.out.println(isRotational(permutation1,permutation2));
}

private static boolean isRotational(String permutation1,String permutation2){

while(permutation1.charAt(0) != permutation2.charAt(0))
permutation2 = rotate(permutation2);

return permutation1.equalsIgnoreCase(permutation2);
}

private static String rotate(String permutation){

char[] charArray = permutation.toCharArray();

int len = charArray.length;
char temp = charArray[len-1];

for(int idx = len-1;idx > 0;idx--)
charArray[idx] = charArray[idx-1];

charArray[0] = temp;

return new String(charArray);
}

}

public class CheckeTwoStringSame {
	public static void main(String[] args) {
		char[] base = "password".toCharArray();
		char[] current = "ordpassw".toCharArray();
		boolean b = checkAfterRotation(base, current, 0, current.length);
		System.out.println("After rotation Two strings are same or not ?  " + b);

	}

	private static boolean checkAfterRotation(char[] base, char[] current , int start, int length) {
		if (start < length - 1) {
			if (String.valueOf(base).equals(String.valueOf(current))){
				return true;
			} else {
				return checkAfterRotation(base, rotateRightToLeft(current), ++start, current.length);
			}
		}
		return false;
		
	}

	private static char[] rotateRightToLeft(char[] items) {
		char temp;
		temp = items[0];
		for (int i = 0; i < items.length - 1; i++) {
			items[i] = items[i + 1];
		}
		items[items.length - 1] = temp;
		return items;

	}
}

have two queue. offer string1 elements inside queue1. and stirng2 in queue2. start popping queue2 and adding in queue2 only unless u find first element of queue1.
start poping both queues if queue1 is popped completely then return true. otherwise return false.
Also terminate loop once u poppedup all element in queue but din't find match and return false.

1 #include <cassert>
2 #include <exception>
3 #include <fstream>
4 #include <iostream>
5
6 #include "Library/functions.h"
7
8 #include <ucontext.h>
9 #include <stdio.h>
10 #include <stdlib.h>
11

12 using namespace std;
13
14 // Write a function to check whether the two strings are rotation of each other or not.
15 // Example: str1="Password" str2="ordPassw"
16
17 bool checkRotation(const string& str1, const string& str2) {
18 size_t pos = 0;
19 for (int i = 0; i < str2.length(); i++) {
20 if (0 == i) {
21 pos = str1.find(str2[0]);
22 if (string::npos == pos)
23 return false;
24 } else {
25 pos++;
26 pos %= str1.length();
27 if (str1[pos] != str2[i])
28 return false;
29 }
30 }
31 return true;
32 }
33
34 int main(int argc, char **argv) {
35 assert(checkRotation("Password", "ordPassw"));
36 assert(!checkRotation("Password1", "ordPassw"));
37 return 0;
38 }

12 using namespace std;
 13 
 14 // Write a function to check whether the two strings are rotation of each other or not.
 15 // Example: str1="Password" str2="ordPassw" 
 16 
 17 bool checkRotation(const string& str1, const string& str2) {
 18     size_t pos = 0;
 19     for (int i = 0; i < str2.length(); i++) {
 20         if (0 == i) {
 21             pos = str1.find(str2[0]);
 22             if (string::npos == pos)
 23                 return false;
 24         } else {
 25             pos++;
 26             pos %= str1.length();
 27             if (str1[pos] != str2[i])
 28                 return false;
 29         }
 30     }
 31     return true;                                                                                                  
 32 }
 33 
 34 int main(int argc, char **argv) {
 35     assert(checkRotation("Password", "ordPassw"));
 36     assert(!checkRotation("Password1", "ordPassw"));
 37     return 0;
 38 }

#include<stdio.h>
#include<conio.h>
#include<string.h>
void main()
{
char s1[10],s2[10],rstr[10];
int i,j,k,n,x,y;
clrscr();
printf("enter first string\n ");
scanf("%s",s1);
printf("enter second string\n");
scanf("%s",s2);
x=strlen(s1);
y=strlen(s2);
if(x!=y)
printf("strings are not permutation of each other");
else
for(i=0;i<x;i++)
{
for(j=0;j<x;j++)
{
if(s1[i]==s2[j])
{
s2[j]=0;
break;
}
}
}
for(i=0;i<x;i++) {
if(s2[i]!=0)
{
printf("strings are not match");
break;
}
if(i!=x-1)
continue;
printf("string are matched");
}
getch();
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main ()
{

	char *str = "pass@1wOrd$";
	char *rev  = "@1Ordpassw$";
	int i=0,strTotal=0,revTotal=0;

	if(strlen(str) != strlen(rev))
	{
		printf(" Error : Different String length\n");
		return 0;
	}

	while(str[i] != '\0')
	{
        strTotal += str[i];
		revTotal += rev[i];
		i++;
	}
	if(strTotal == revTotal)
		printf(" String is rotation of the 2nd String\n");
	else
			printf(" String is not rotation of the 2nd String\n");


	return 0;


}

Write a program to find the reoccurence the character in a given string ,if it find in that given string , come out from the loop.

For Example
char *str = "abcdefgha";
here a is occured second time, so comes out from the loop.

/* Function checks if passed strings (str1 and str2)
   are rotations of each other */
int areRotations(char *str1, char *str2)
{
  int size1   = strlen(str1);
  int size2   = strlen(str2);
  char *temp;
  void *ptr;
 
  /* Check if sizes of two strings are same */
  if (size1 != size2)
     return 0;
 
  /* Create a temp string with value str1.str1 */
  temp   = (char *)malloc(sizeof(char)*(size1*2 + 1));
  temp[0] = '\0';
  strcat(temp, str1);
  strcat(temp, str1);
 
  /* Now check if str2 is a substring of temp */
  ptr = strstr(temp, str2);
 
  free(temp); // Free dynamically allocated memory
 
  /* strstr returns NULL if the second string is NOT a
    substring of first string */
  if (ptr != NULL)
    return 1;
  else
    return 0;
}

public class StringExample {
public static void main(String [] args){
String s1="Password";
String s2="ordPassw";
int flag=0;
if(s1.length()==s2.length()){
int pos=s2.indexOf(s1.charAt(0));
for(int i=0;i<s1.length()-1;i++){
if(s2.charAt(pos)==s1.charAt(i))
flag=1;
else
flag=0;
if(pos==s1.length()-1)
pos=0;
else
pos+=1;

}
}
if(flag==1)
System.out.println("rotated string");
else
System.out.println("invalid string");

}

}

In C#

string str1 = "Password", str2 = "drowssaP";
Console.WriteLine("String rotation of each other: " + str1.SequenceEqual(str2.Reverse()));

1. If length of strings is different return false.
2. If first str1 character is not in str2, return false.
3. If character is in str2, iterate str2 from that position and check next character. Keep iterating both strings while characters match.
4. If next character in str1 != next character in str2, compare str1 character with index[0] in str2. If str2[0] matches then continue, iterating str2 from 0.
5. If a letter is duplicated it's possible to get a false starting point in str2, so if the first character is in str2 multiple times then save starting position and if we get a negative result then try again with the next occurrence of str1[0]. E.g. if str1 == "poppingPass" and str2 == "pingPasspop" then we would find the correct starting point on the second attempt. If str1 == "poppingPasspopped" and str2 == "poppedpoppingPass" then we would find the current starting point on the fourth attempt, so might not be great worst case complexity with many duplicated letters.

My solution

bool isRotation( string& str1, string& str2 )
{
if (str1.length() != str2.length() )
return false;

for ( int i = 0; i < str2.length(); i++ )
{
if ( str1[0] == str2[i] )
{
int j;
int k = (i+1)%str1.length();
for( j = 1; j < str1.length(); j++ )
{
if ( str1[j] != str2[k] )
break;
k = (k+1)%str1.length();
}
if(j == str1.length())
return true;
}
}
return false;
}

bool isEqual(string a, string b){
        if (a.size() != b.size()) return false;
        if (a.empty() || a == b) return true;
        string temp="a"; // random character since we assign to first element later
        for (int k = 0; k < b.size(); k++){
            temp[0] = a.back();
            a.pop_back();
            temp += a;
            if (temp == b) {
                return true;
            }
            a = temp;
            temp = "a";
        }
        return false;
    }