Jul 312012
 

Given two strings, write code to check if one string is rotation of another. For example: str2 below is a rotation of str1.

str1 = "ROTATE"
str2 = "TATERO"

You may use the strstr function, but ONLY ONCE.

Algorithm:

If two strings have different number of characters
    return FALSE
Concatenate str1 with itself and store it in str3
    (str3 = CONCATENATE(str1,str1))
If str2 is sub string of str3, 
    return true
else
    return false

In above example,

str3 = concatenate ("ROTATE", "ROTATE")
     = ROTATEROTATE
"TATERO" is substring of "ROTATEROTATE", hence true

 Code:


    /* Function to check if a string is rotation of another string or not
     */
    bool isRotate(char *str1, char *str2)
    {
        if(strlen(str1) != strlen(str2))
            return false;

        char *str3 = (char*) malloc(2*strlen(str1) + 1);
        strcpy(str3, str1);
        strcat(str3, str1);
        
        // Need this variable because memory allocated to str3 need to be freed
        bool bIsRotate = false;
        if(strstr(str3, str2) != NULL)
            bIsRotate = true;

        // Freeing the memory allocated to temporary string
        free(str3); 

        return bIsRotate;
}
 

 

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)