isRotation.py

"""
Example: strOne = dingReviewCo, strTwo = CodingReview
Here rotation is after "ReviewCo"

Suppose we split strTwo at the rotation point into a and b
where a = "Co" and b = "dingReview"
Then, strOne would be ba and strTwo would be ab

strOne = dingReviewCo = b + a = ding + ReviewCo
strTwo = CodingReview = a + b = Co + dingReview

We can see from this that ba will always be a substring of ab + ab,
∴, strOne will always be a substring of strTwo + strTwo.

Solution: check of strOne is a rotation of strTwo
by checking if strOne is a substring of strTwo + strTwo
"""

# Helper function
def isSubString(strOne, strTwo):
  return strOne in strTwo

# Solution
def isRotation(strOne, strTwo):
  return isSubString(strOne, strTwo + strTwo)


"""
Time and Space Complexity:

isSubString:
O(n + m)

isRotation:
O(n + m) where n = length of strOne and m = length strTwo
strTwo + strTwo concatination takes O(m) time
∴, time complexity and space complexity are both O(n + m)
"""