I ran into a quite interesting problem several days ago. I had a hard time solving it. So I post it here, FYI.
Assume you have a method "isSubstring" which checks if one word is a substring of
another. Given two strings, s1 and s2, write code to check if s2 is a rotation of s1
using only one call to "isSubstring".
(e.g., "waterbottle" is a rotation of "erbottlewat").
Any ideas?
What dose "rotation" mean? Well, you find a break point in a string, you break the string into two parts, you recombine the two parts in reversed order, and now you get a rotation of the original string. For the example given in the problem definition:
wat ^ erbottle ————> erbottle + wat ————> erbottlewat
Given a string S, we break it into two parts which are labeledX and Y. That is, S=XY (figuratively). After rotating, we get another string T=YX. It's so damn easy if you are only asked to rotate a string, huh~ What about the other way around? Of course you can immediately think of enumerating through all the possible break points and call "isSubstring" at each break point. Since the problem limits the call of "isSubstring" to only once, this approach is not desirable. Instead, we try to figure out the underlying pattern regardless of the actual position of the break point.
One thing worthing noticing is that T=YX is actually a substring of SS=XYXY, obviously. That is to say, by making a rotation of S, you can get a substring of SS=XYXY. And it's quite convenient to construct the string U=XYXY, just concatenate an S after the original S. So without sweating, we can tell weather the string you wanna check, say S', is a substring of SS=XYXY. So how's this related to our problem?
Theorem: If S' is a substring of SS, then S` is a rotation of S.
Proof:
Negative assumption: S` is not a rotation of S.
Let S`=BC
since S` is a substring of SS, we can get:
SS=aBCd, where a,d may be empty strings.
according to the assumption:
CB!=S
and consequently:
CBCB!=SS
thus
CS`B!=SS
as a result, S` is not a substring of SS, which conflicts the known condition,
and the assumption is denied, S` is a rotation of S.
One more thing: the relation is a rotation of is equivalent, which means:
[1]Reflexivity: S is a rotation of S itself;
[2]Symmetry: if S is a rotation of T, then T is a rotation of S;
[3]Transitivity:if R is a rotation of S and S is a rotation of T, then R is a rotation of T.
Now it seems trivial to write any code.
#python
def isRotate(s1, s2):
return isSubstring(s1, s2+s2)
