Created
August 4, 2021 03:53
-
-
Save o-az/7bbb29502a8fb179dc219f9a3c5c94fa to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
""" | |
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) | |
""" |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment