Microsoft Interview Question
Software Engineer / DevelopersI guess we cannot assume if it is right or left rotated...so do the operation for s1,s2 and in the opposite order i.e. s2,s1.
The above algorithm does not handle the following case:
str1 = ABCD
str2 = DABC
this should return false, whereas using above would return true.
strcat(str1, str1) = ABCDABCD
str2 = DABC <-- exists in the concatenated string.
Solution:
After concatenation, always compare from the index of half of the length of str1 to the max length of str2.
DABC is valid. it should return true.
if(strlen(s1) == strlen(s2))
return strstr(strcat(s1,s1),s2);
else
return false;
We cant always assume that the string is right rotated. to check if str2 is left rotation of str1, then use,
strstr(strcat(strrev(str1),strrev(str1)), str2)
The question is simpler than it sounds. Just call:
- K February 01, 2007strstr(strcat(s1,s1), s2)
so if the string is ABCD, the concatination will make it ABCDABCD and hence any rotation will fall within the concatenated string.