String Rotation

January 31, 2012

We have today another question from our never-ending supply of interview questions:

Write a function that takes two input strings and determines if one is a rotation of the other. For instance, “ProgrammingPraxis” and “PraxisProgramming” are rotations of each other, but “ProgrammingPrasix” is not a rotation of “ProgrammingPraxis” because the last three letters are out of order.

Your task is to write the requested function. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

20 Responses to “String Rotation”

1. Tante Hedwig said

```import Data.List
rotation s1 s2 = s1 `isInfixOf` (s2++s1)
```
2. Tante Hedwig said

Besser so:

```isRotation s1 s2 =  (length s1 == length s2) && s2 `isInfixOf` (s1++s1)
```
3. having an easy way to rotate strings in APL, rotating only those amounts that would make the first characters match seemed like a neat little optimization:

isRotation←{1∊⍺∘≡¨(¯1+{⍵/⍳⍴⍵} ⍵=⍬⍴⍺)∘.⌽⊂⍵}

but, the length match test, and the looking within a concatenated pair of the target is much neater, without the messy match and actual rotates.

isRotation2←{~(⍴⍺)≡⍴⍵:0 ⋄ 1∊⍺⍷⍵,⍵}

4. Amir said

The written code in C:

#include
#include
#include

int is_rotate(char* str1, char* str2){
int newlen = (strlen(str1) == strlen(str2)) ? 2*strlen(str1) : 0;
if (!newlen)
return 0;

char* str_concat = (char*) malloc( newlen + 1);
strcpy(str_concat, str1);
strcat(str_concat, str1);
str_concat [newlen] = ”;

printf(“String1: %s\n”, str1);
printf(“String2: %s\n”, str2);
printf(“Concats: %s\n\n”, str_concat);

char* substr = strstr(str_concat, str2);
if (!substr)
return 0;
else
return 1;
}

int main() {
char string1[] = “Hi_Amir_How_Are_You_Amir_”;
char string2[] = “How_Are_You_Amir_Amir_Hi_”;
char string3[] = “How_Are_You_Amir_Hi_Amir_”;

printf(“===> Str1 & Str2 Are%s Equal.\n\n”, (is_rotate(string1, string2)) ? “” : ” \”NOT\”");
printf(“===> Str1 & Str3 Are%s Equal.\n\n”, (is_rotate(string1, string3)) ? “” : ” \”NOT\”");

return;
}

5. Dan Schoch said

Okay, Mr. Programming Praxis – here’s my brute force approach, using PL/SQL. (I should have read your elegant solution first.)

```declare
s1      constant varchar2(100)  := 'ProgrammingPraxis' ;
s2      constant varchar2(100)  := 'PraxisProgramming' ;
stmp             varchar2(100) ;
begin
-- get rid of unequal length strings
if  length(s1) <> length(s2) then
dbms_output.put_line(s1||' is NOT a rotation of '||s2) ;
return ;
end if ;

-- rotate string2 and compare strings
stmp := s2 ;
for i in 1..length(s1)
loop
stmp := substr(stmp,2,length(stmp))||substr(stmp,1,1) ;
if  s1 = stmp then
dbms_output.put_line(s1||' is a rotation of '||s2) ;
return ;
end if ;
end loop ;
dbms_output.put_line(s1||' is NOT a rotation of '||s2) ;
end ;
/
ProgrammingPraxis is a rotation of PraxisProgramming
```
6. Georg said

Here is one solution in C which does not require memory allocation and string concatenation:

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

int is_rotate(const char* str1, const char* str2)
{
const int len = strlen(str1);
if (strlen(str2) == len)
{
int offset, i;
for (offset = 0; offset < len; ++offset)
{
for (i = 0; i < len; ++i)
{
if (str1[i] != str2[(i+offset)%len])
break;
}
if (i==len)
return 1;               /* found rotation */
}
}
return 0;
}

int main(void)
{
char str1[] = "ProgrammingPraxis";
char str2[] = "PraxisProgramming";
char str3[] = "PraxsiProgramming";

printf("str1 & str2 are%s equal.\n", (is_rotate(str1, str2)) ? "" : " NOT");
printf("str1 & str3 are%s equal.\n", (is_rotate(str1, str3)) ? "" : " NOT");
}
```
7. Apparently I had the same idea as Georg.

```def is_rot(s, t):
n = len(s)
if len(t) != n:
return False
for k in range(0, n):
ok = True
for i, ch in enumerate(s):
if ch != t[(i + k) % n]:
ok = False
break
if ok:
return True
return False

if __name__ == "__main__":
cases =  [ ("ProgrammingPraxis", "PraxisProgramming", True),
("ProgrammingPraxis", "PrasixProgramming", False),
("aab", "aba", True),
("bbaa", "baba", False) ]
for c in cases:
print("OK" if is_rot(c[0], c[1]) == c[2] else "Fail")
```
8. homanhduc said

THis is how I did in C++, [look amateur]:

#include
#include
using namespace std;

bool isRotateString(string, string);

int main()
{
string s1,s2;
cout <> s1;
cout <> s2;
if ((isRotateString(s1,s2)) == true)
cout << "YES!!!";
else cout <= 0; –i)
{
c = s1[i];
if (s1[i] == toupper(c))
{
rString += s1.substr(i, m – i);
m -= (m – i);
}
}

cout << "Rotated string : " << rString << endl;

if (rString == s2)
return true;
else return false;

}
}

9. homanhduc said
```#include <iostream>
#include <string>
using namespace std;

bool isRotateString(string, string);

int main()
{
string s1,s2;
cout << "Input string 1: ";
cin  >> s1;
cout << "Input string 2: ";
cin >> s2;
if ((isRotateString(s1,s2)) == true)
cout << "YES!!!";
else cout << "NO!!!";
return 0;
}

bool isRotateString(string s1, string s2)
{
//have to be same length at first
if (s1.length() != s2.length())
return false;
//yeah same length, now what?
else
{
string rString = "";
int i, m = s1.length();
char c;
//starting from the very-end
for (i = s1.length()-1; i >= 0; --i)
{
c = s1[i];
if (s1[i] == toupper(c))
{
rString += s1.substr(i, m - i);
m -= (m - i);
}
}

cout << "Rotated string : " << rString << endl;

if (rString == s2)
return true;
else return false;

}
}
```
10. Axio said

Geez. I had forgotten how painful it is to write in imperative languages, especially when one has to do everything manually!
Language is Ada (because C should be forbidden.)
I used a concatenation approach instead of modulo, for no special reason.

```with Ada.Text_IO;

procedure Rotate is

function RotateF (S1: in String ; S2: in String) return Boolean is
FFFOUND : exception;
NOPE : exception;
S3 : String := S2 & S2;
Pos : Integer := 1;
Cur : Integer;

begin
if S1'Length /= S2'Length
then
return False;
end if;

for Pos in 1..S1'Length loop
Cur := 0;
begin
while Cur < S1'Length loop
if S1(1+Cur) /= S3(Pos+Cur)
then
raise NOPE;
end if;
Cur := Cur + 1;
end loop;
raise FFFOUND;
exception
when NOPE => null;
end;
end loop;
return(False);

exception
when FFFOUND => return(True);
end RotateF;

begin
if RotateF(Argument(1),Argument(2))
then
else
end if;
end Rotate;
```
11. Axio said

Common Lisp FTW \o/

```(defun rotatep (s1 s2)
(and (= (length s1) (length s2))
(loop for i below (length s1)
when (loop for j below (length s1)
when (not (char= (aref s1 (mod (+ i j) (length s1)))
(aref s2 j)))
return nil
finally (return t))
return t)))
```
12. Jussi Piitulainen said

What a cool trick the model answer is. Before seeing it, I thought the problem merely tedious.

Here is an expansive answer, just for fun. (Python 3 it is.)

```def is_rotated(s, t):
return ( { s[k:] + s[:k] for k in range(len(s)) } ==
{ t[k:] + t[:k] for k in range(len(t)) } )
```
13. Mike said

In python, the obvious solution is:

```
def is_rotation(s1, s2):
return s1 in s2+s2

```

An alternative:

import re

def is_rotation(s1, s2):
return any(s1.startswith(s2[i:]) and s1.endswith(s2[:i]) for i in (mo.start() for mo in re.finditer(s1[0], s2)))

14. programmingpraxis said

Mike: In your first solution, you must also check that the two strings are the same length. Otherwise, you will erroneously report that the two strings are rotations if s1 is a substring of s2.

15. agentultra said

It appeared to me in the description that the rotation function is based on words in the string and not the string itself, so I wrote a solution that splits the string into words and compares the reverse of the second to the first: http://codepad.org/G1ws5Bu3

It is somewhat generic; allowing the user to pass in a function that interprets whether a given character in the string is a delimiter and whether to include said delimiter as part of the word.

For trivial functions like this I tend to write doctests since they’re pretty quick for getting you started. Documentation also flows a little more naturally with them as you explore the various cases.

16. ardnew said

hot perl action using OPs wizardry:

```sub is_rotation(\$\$)
{
return length(\$_[0]) == length(\$_[1]) && (\$_[0] x 2) =~ m/\$_[1]/;
}
```
17. Manoj Senguttuvan said

simply-C-ty :P

```#include<stdio.h>
#include<string.h>
int main(int argc,char* argv[])
{
int i=0,index1=1,index2=1,flag=1;
for(;index1<strlen(argv[1]);index1++)
if(argv[1][index1]>=65 && argv[1][index1]<=90)
break;
for(;index2<strlen(argv[2]);index2++)
if(argv[2][index2]>=65 && argv[2][index2]<=90)
break;
for(;i<index1;i++)
if(argv[1][i]!=argv[2][index2+i])
flag=0;
for(i=0;i<index2;i++)
if(argv[2][i]!=argv[1][index1+i])
flag=0;
printf("%sString Rotation",strlen(argv[1])!=strlen(argv[2])||flag==0?"Not ":"");
}
```
18. Nick said

isRotation(String str1,String str2)

//Check lengths
if(length(str1)!=length(str2))
return false
end if
else
//concat the string with itself and check if the concatenated string is a substring of str1
String str3=str2+str2
return str3.contains(str1)
end else

//method in java

public boolean isRotation(String str1,String str2)
{
if(str1.length()!=str2.length())
return false;
else
{
String str3=str2+str2;
return str3.contains(str1);
}
}

19. Raju said

I liked Nick’s solution!
Here I’ve tried it to solve using regex in Java.

My first submission!

```
package raju;

import java.util.ArrayList;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class RotationalStringMatch {

public static void main(String[] args){
String firstString = args[0];
String secondString = args[1];

if(firstString.length() != secondString.length()){
System.out.println("Input String lengths are not matching. Please enter valid strings of same length.");
System.exit(0);
}

ArrayList<String> firstStringSplitList = formSplitStringList(firstString);
ArrayList<String> secondStringSplitList = formSplitStringList(secondString);

if(  (firstStringSplitList.size() > 2) || (secondStringSplitList.size() > 2)) {
System.out.println("More than two words in a String. Please check input String");
System.exit(0);
}

String reverseFirstString = firstStringSplitList.get(1) + firstStringSplitList.get(0);
if(reverseFirstString.equals(secondString))
System.out.println("Match found. Both Strings are word reversly equal");
else
System.out.println("No match. Words in input strings are different. Give valid input strings!");
}

public static ArrayList<String> formSplitStringList(String inputString){
Pattern p = Pattern.compile("[A-Z]{1}[a-z]*");
Matcher m = p.matcher(inputString);

ArrayList<String> stringSplitList = new ArrayList<String>();
while(m.find()){
}

return stringSplitList;
}
}
```
20. Ted said

Using substrings in Java:

public static boolean Stringrot(String s1, String s2){
int cnt = 0;
if(s1.length() !=s2.length()){
return false;
}
while(cnt<s1.length() && s2.contains(s1.substring(0,++cnt))){}
if(s2.contains(s1.substring(cnt-1))){
return true;
}
else{
return false;
}
}