Find height of the Binary Tree
July 31, 2012
Recursive function to reverse a String
August 7, 2012

Check if one string is rotation of another

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

Your email address will not be published. Required fields are marked *