Teaching Kids Programming – Rotation of Another String

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given two alphabet (can be lower and/or uppercase) strings s0 and s1, determine if one is a rotation of the other.

Constraints
1 ≤ n ≤ 200,000 where n is the length of s0
1 ≤ m ≤ 200,000 where m is the length of s1
Example 1
Input
s0 = “Cattywampus”
s1 = “sCattywampu”
Output
True

Example 2
Input
s0 = “Gardyloo”
s1 = “dylooGar”
Output
True
Explanation
This string is rotated on Gar and dyloo

Example 3
Input
s0 = “Taradiddle”
s1 = “diddleTara”
Output
True
Example 4
Input
s0 = “Snickersnee”
s1 = “Snickersnee”
Output
True
Explanation
This one is tricky but it’s still a rotation, between “ and Snickersnee

Bruteforce Algorithm to Check If String is Rotation of Another

We can bruteforce one string’s all rotation and check if it is same as another. This takes O(N^2) time – and remember if two strings are different sizes, we don’t need to check at all – as it is impossible.

1
2
3
4
5
6
7
8
9
10

class Solution:
    def isRotationOf(self, s0, s1):
        n, m = len(s0), len(s1)
        if n != m:
            return False
        for _ in range(n):
            s1 = s1[1:] + s1[0]
            if s1 == s0:
                return True
        return False

class Solution:
    def isRotationOf(self, s0, s1):
        n, m = len(s0), len(s1)
        if n != m:
            return False
        for _ in range(n):
            s1 = s1[1:] + s1[0]
            if s1 == s0:
                return True
        return False

Check in All String Rotations

Given “abc” its rotated strings are “abc”, “bca” and “cab”. Thus all three variations are contained in “abc” + “abc”. Therefore, we can simply check if one string is substring of another string which is concatenated twice.

1
2
3
4
5

class Solution:
    def isRotationOf(self, s0, s1):
        if len(s0) != len(s1):
            return False
        return s0 in s1 + s1

class Solution:
    def isRotationOf(self, s0, s1):
        if len(s0) != len(s1):
            return False
        return s0 in s1 + s1

The time complexity is O(N) or better if using KMP string search.

See also: String Clockwise Shift Algorithm

–EOF (The Ultimate Computing & Technology Blog) —