Leetcode – Rotate String Solution in Python

Spread the love

String manipulations are a fundamental aspect of algorithmic challenges, often testing a programmer’s ability to recognize patterns, utilize basic data structures, and leverage the inherent properties of strings. Among these, the problem of determining if one string can be rotated to form another is an interesting one. Found on platforms like Leetcode, the “Rotate String” problem is an excellent representative of this category.

In this comprehensive discussion, we will dissect the “Rotate String” problem, understand its requirements, and provide Python solutions ranging from the intuitive brute-force to more optimized approaches.

Problem Statement

Given two strings A and B, check if B can be obtained by rotating A any number of times (including zero).

Example:

Input: A = "abcde", B = "cdeab"
Output: True

Clarification:

  • A rotation on A consists of moving the leftmost character of A to the rightmost position. For instance, if A = 'abcde', then it will become 'bcdea' after one rotation.

Understanding the Problem

At the core, we need to discern if B is a rotation of A. A simple insight is that if we were to append A with itself, any possible rotation of A would now be a substring of this new string. Thus, the problem can be reduced to a substring search.

Solution Approaches

Brute Force Approach

  1. Concatenate string A with itself.
  2. Check if B is a substring of the concatenated string using a substring search.

Optimized Approach using KMP (Knuth-Morris-Pratt) Algorithm

While the brute-force substring search works, its worst-case time complexity can be O(n^2). The Knuth-Morris-Pratt (KMP) algorithm offers an O(n) solution for substring search, making it a more efficient approach for this problem.

Python Solutions

Brute Force Solution:

def rotateString(A: str, B: str) -> bool:
    if len(A) != len(B):
        return False
    return B in A + A

# Example Usage
A = "abcde"
B = "cdeab"
print(rotateString(A, B))  # Expected output: True

Optimized Solution using KMP:

def kmp_table(pattern):
    ''' Generate the KMP table for a given pattern '''
    table = [0] * len(pattern)
    j = 0
    for i in range(1, len(pattern)):
        if pattern[i] == pattern[j]:
            j += 1
            table[i] = j
        elif j > 0:
            j = table[j-1]
            i -= 1
        else:
            table[i] = 0
    return table

def kmp_search(text, pattern):
    ''' Implement the KMP search algorithm '''
    table = kmp_table(pattern)
    i = j = 0
    while i < len(text) and j < len(pattern):
        if text[i] == pattern[j]:
            i += 1
            j += 1
        elif j == 0:
            i += 1
        else:
            j = table[j-1]
    return j == len(pattern)

def rotateString(A: str, B: str) -> bool:
    if len(A) != len(B):
        return False
    return kmp_search(A + A, B)

# Example Usage
A = "abcde"
B = "cdeab"
print(rotateString(A, B))  # Expected output: True

Complexity Analysis

Brute Force Solution:

Time Complexity: O(n) for checking if B is a substring of A+A, where n is the length of the string.

Space Complexity: O(n) as we create a new string by concatenating A with itself.

Optimized Solution:

Time Complexity: O(n) where n is the length of the string. The KMP algorithm provides linear-time substring searching.

Space Complexity: O(n) for the KMP table.

Conclusion

The “Rotate String” problem serves as an ideal example of how a seemingly complex task can be boiled down to a simpler problem (i.e., substring searching) by employing critical insights about the problem’s nature. Moreover, it emphasizes the value of understanding and utilizing efficient algorithms (like KMP) to further optimize a solution.

Leave a Reply