5 Best Ways to Check if One String Can Be Shifted Clockwise to Another in Python

Rate this post

πŸ’‘ Problem Formulation: The task at hand involves determining if it’s possible to convert one string to another by shifting its characters clockwise. For example, with the input strings “abcde” and “deabc”, the desired output is true, since rotating “abcde” three positions clockwise yields “deabc”.

Method 1: Brute Force Rotation

This method involves rotating the first string one character at a time and checking after each rotation if it matches the second string. It’s a straightforward approach where we define a function can_shift_to() that will handle the successive rotations and comparisons until a match is found or all rotations have been tried.

Here’s an example:

def can_shift_to(s1, s2):
    if len(s1) != len(s2):
        return False
    for i in range(len(s1)):
        if s1[i:] + s1[:i] == s2:
            return True
    return False

# Test the function
s1 = 'abcde'
s2 = 'deabc'
print(can_shift_to(s1, s2))

Output:

True

This code snippet checks if two strings are rotations of each other by incrementally rotating s1 and comparing it with s2. If a match is found, it returns True; otherwise, after all possible rotations, it returns False.

Method 2: Use String Concatenation

If a string can be shifted clockwise to become another string, then the second string must be a substring of two copies of the first string concatenated together. This method checks exactly that in a single line of code within the function is_rotation().

Here’s an example:

def is_rotation(s1, s2):
    return len(s1) == len(s2) and s2 in (s1 + s1)

# Test the function
s1 = 'abcde'
s2 = 'deabc'
print(is_rotation(s1, s2))

Output:

True

This code snippet concatenates s1 with itself and then checks if s2 is a substring within this new string, effectively checking all cyclic rotational positions in a single operation.

Method 3: Using Python’s deque

Python’s collections.deque data structure can be used to efficiently rotate elements. The rotate() function of deque can be used to shift the elements of the string and then compare with the target string.

Here’s an example:

from collections import deque

def deque_rotation(s1, s2):
    if len(s1) != len(s2):
        return False
    d = deque(s1)
    for i in range(len(s1)):
        d.rotate(1)
        if ''.join(d) == s2:
            return True
    return False

# Test the function
s1 = 'abcde'
s2 = 'deabc'
print(deque_rotation(s1, s2))

Output:

True

With this snippet, s1 is loaded into a deque, and then rotated one position at a time for comparison to s2. If a match occurs, it returns True. Otherwise, the function returns False after all rotations have been tried.

Method 4: Index Mapping

This method finds the index of the starting character of the second string in the first string and then verifies the subsequent characters by iterating over the strings with modular arithmetic.

Here’s an example:

def index_mapping_rotation(s1, s2):
    if len(s1) != len(s2) or not s1:
        return False
    start = s1.find(s2[0])
    if start == -1:
        return False
    n = len(s1)
    for i in range(n):
        if s1[(start + i) % n] != s2[i]:
            return False
    return True

# Test the function
s1 = 'abcde'
s2 = 'deabc'
print(index_mapping_rotation(s1, s2))

Output:

True

In the snippet, index_mapping_rotation() initializes the mapping with the first match of characters. Then, it validates all subsequent characters, allowing for wrapping around the end of the string with the modulus operator.

Bonus One-Liner Method 5: Quick Check

This succinct approach combines string length comparison and substring checking into a one-liner function. It’s a terser version of the second method.

Here’s an example:

is_rotated = lambda s1, s2: len(s1) == len(s2) and s2 in s1 * 2

# Test the function
s1 = 'abcde'
s2 = 'deabc'
print(is_rotated(s1, s2))

Output:

True

This compact code employs a lambda function to conduct the identical concatenation and substring search logic of Method 2, to determine if one string is a rotation of the other.

Summary/Discussion

  • Method 1: Brute Force Rotation. Simple and intuitive. Time-consuming for long strings. Iterates up to n times.
  • Method 2: Use String Concatenation. Clever and efficient. Uses Python’s powerful string handling. Only one iteration needed.
  • Method 3: Using Python’s deque. Utilizes deque’s efficient rotational abilities. Still requires up to n rotations and associated comparisons.
  • Method 4: Index Mapping. Direct and effective. Leverages the structure of rotations mathematically. Only runs if the starting character is found.
  • Bonus One-Liner Method 5: Quick Check. Extremely concise. Perfect for one-off checks. May not be as clear for those new to Python’s capabilities.