796. Rotate String

Intuition

To check if one string is a rotation of another, we can double the original string. If the rotated version exists, it must appear as a substring within this doubled string.

Complexity

Space Complexity
Time Complexity

O(N)\text{O}(N)

O(N2)\text{O}(N^2)

Code

public boolean rotateString(String original, String target) {
    // Edge case: if lengths differ, rotation is not possible
    if (original.length() != target.length()) return false;

    // Create a doubled version of the original string
    String doubledOriginal = original + original;
    int originalLength = original.length();

    // Check all substrings of length originalLength in doubledOriginal
    for (int i = 0; i < originalLength; ++i) {
        // Extract substring and compare it with target
        if (doubledOriginal.substring(i, i + originalLength).equals(target)) {
            return true; // Found a match; it's a valid rotation
        }
    }

    return false; // No valid rotation found
}

Last updated