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.

Posted by programmingpraxis

Filed in Exercises

22 Comments »

22 Responses to “String Rotation”

Tante Hedwig said

January 31, 2012 at 10:00 AM

In Haskell:

import Data.List
rotation s1 s2 = s1 `isInfixOf` (s2++s1)

Tante Hedwig said

January 31, 2012 at 10:04 AM

Besser so:

isRotation s1 s2 =  (length s1 == length s2) && s2 `isInfixOf` (s1++s1)

Randy A MacDonald said
January 31, 2012 at 4:02 PM
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∊⍺⍷⍵,⍵}
Amir said
January 31, 2012 at 6:21 PM
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;
}

Dan Schoch said

January 31, 2012 at 7:00 PM

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

Georg said

January 31, 2012 at 9:24 PM

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");
}

Tomasz Kwiatkowski said

January 31, 2012 at 10:37 PM

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")

homanhduc said
January 31, 2012 at 10:48 PM
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;

}
}

homanhduc said

January 31, 2012 at 10:54 PM

#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;
		
	}
}

Axio said

February 1, 2012 at 5:55 AM

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;
with Ada.Command_line; use Ada.Command_Line;

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
    Ada.Text_IO.Put_line("tation!Ro");
  else
    Ada.Text_IO.Put_line("Not a rotation!");
  end if;
end Rotate;

Axio said

February 1, 2012 at 6:07 AM

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)))

Jussi Piitulainen said
February 1, 2012 at 8:29 AM
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)) } )
```
Mike said
February 2, 2012 at 9:00 AM
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)))
programmingpraxis said
February 2, 2012 at 1:40 PM
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.
agentultra said
February 3, 2012 at 5:03 AM
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.

ardnew said

February 3, 2012 at 5:13 PM

hot perl action using OPs wizardry:

sub is_rotation($$)
{
  return length($_[0]) == length($_[1]) && ($_[0] x 2) =~ m/$_[1]/;
}

Manoj Senguttuvan said

February 23, 2012 at 12:26 PM

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 ":"");
}

Nick said
February 23, 2012 at 6:38 PM
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);
}
}

Raju said

February 29, 2012 at 12:43 AM

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()){
			stringSplitList.add(m.group());
		}
		
		return stringSplitList;
	}
}

Ted said
August 11, 2012 at 3:47 AM
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;
}
}
Lal said
June 19, 2014 at 7:46 PM
Let the given two strings are string1 and string2. We have to check whether string2 is a rotation of string1. The algorithm works as :

Check the length of the two strings. If they are not same, return false.
Otherwise, concatenate string1 with itself and check whether string2 is a substring of it.

For explanation and code http://www.algoqueue.com/algoqueue/default/view/7208960/check-whether-one-string-is-a-rotation-of-another
Zoran said
February 6, 2015 at 5:36 PM
@Lal
I have tried both methods. The second method does not work for the word combination “affenzoo” vs. “zooaffen”. (i.e. monkey zoo).
Can you clarify?

Thank you,

http://pastebin.com/60CusEQc

Programming Praxis

String Rotation

January 31, 2012

22 Responses to “String Rotation”

Leave a comment

Categories

Archives

Archives

Programming Praxis

String Rotation

January 31, 2012

Share this:

Related

22 Responses to “String Rotation”

Leave a comment

Categories

Archives

Archives