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.

About these ads

Pages: 1 2

21 Responses to “String Rotation”

  1. Tante Hedwig said

    In Haskell:

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

  21. Lal said

    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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 629 other followers

%d bloggers like this: