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.
Given two strings
B, check if
B can be obtained by rotating
A any number of times (including zero).
Input: A = "abcde", B = "cdeab" Output: True
- A rotation on
Aconsists of moving the leftmost character of
Ato 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.
Brute Force Approach
- Concatenate string
- Check if
Bis 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.
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 =  * 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
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.
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.
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.