Saturday, April 10, 2010

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)

Syntax of strstr 
const char * strstr ( const char * str1, const char * str2 );

 Returns a pointer to the first occurrence of str2 in str1, or a null pointer if str2 is not part of str1.
The matching process does not include the terminating null-characters.

Approach1
Append str1 to itself and do a strstr for str2. That should work.
(I am assuming strstr looks for string x within string y).
But this fails sometime...for eg. s1 = ABCDA, s2 = BCDA, s2s2 = BCDABCDA
s2s2 now contains s1, but it is not a rotation of s1.
probably other corner cases exist. 

So we can improve it...by first checking whether s1 and s2 have equal number of characters or not.

0 comments:

Post a Comment