How to Efficiently Determine If Two Strings Are Rotations of Each Other?

Checking String Rotation: An Efficient Solution

In an interview for a software developer position, a candidate was posed a challenge: determine if two strings are rotated versions of each other. Specifically, given "s1" and "s2," the task was to verify if "s1" is a modified version of "s2" by rotating its characters.

The Interviewer's Approach

The candidate's response involved finding the longest prefix in "s2" that matched a substring in "s1," which would represent the point of rotation. By dividing "s2" at that point into "s2a" and "s2b," concatenation of "s2a" and "s2b" could be compared to "s1" for equality.

A Simpler Solution

However, the interviewer suggested a more direct approach: ensuring that "s1" and "s2" have the same length and then testing if "s2" is a substring of "s1" concatenated with itself. This method leverages the fact that a rotated string will always be a substring of the original string when concatenated with it.

Java Implementation

In Java, a simple implementation of this solution could look like:

<code class="java">boolean isRotation(String s1, String s2) {
    return (s1.length() == s2.length()) && ((s1 + s1).indexOf(s2) != -1);
}</code>

Efficiency Analysis

This solution's time complexity is O(n), where n is the length of the strings, since it involves a single string concatenation and a substring search on the combined result. The space complexity is O(n) as well, due to the space required for the concatenated string.

By providing a straightforward and efficient method for checking string rotation, this alternative approach meets the interviewer's request for simplicity and effectively detects rotated versions of strings.

The above is the detailed content of How to Efficiently Determine If Two Strings Are Rotations of Each Other?. For more information, please follow other related articles on the PHP Chinese website!