Clicky

Mustafa Veysi Soyvural: Rotation of a String

Sunday, 23 December 2007

Rotation of a String

Q.)Given a string s1 and a string s2, write a snippet to say whether s2 is a
rotation of s1 using only one call to strstr routine?

(eg given s1 = ABCD and s2 = CDAB, return true,
given s1 = ABCD, and s2 = ACBD , return false)

If you add s1by itself then you will get s1=ABCDABCD, as you can see now you will be able to make a decision whether s2 is a rotation or not.

Test Cases:
- s1 = NULL
- s2 = NULL
- Both s1 and s2 are NULL
- s1 = "\0", s2 = "\0" ( the rotation of empty string is itself:) )
- s1 = "ABCD", s2 = "CDAB"
- s1 = "ABCD", s2 = "CD"
- s1 = "ABCD", s2 = "CDBA"
- s1 = "KUJU", s2 = "JUKU"

typedef enum { False, True } Boolean;

Boolean isStringRotate( const char s1[ ], const char s2[ ] ) {
int len1 = 0, len2 = 0;
char *s = NULL;
if ( NULL == s1 || NULL == s2 )
return False;

len1 = strlen( s1 );
len2 = strlen( s2 );
if ( len1 != len2 ) return False;

s = ( char * )malloc( len1 + len2 + 1 );
s[ 0 ] = '\0';
strcat(s, s1);
strcat(s, s1);

if ( !strncmp(&s[ len1 / 2 ], s2, len1) )
return True;
return False;
}

No comments: