如何高效判断两根弦是否互相旋转？

检查字符串旋转：一种有效的解决方案

在软件开发人员职位的面试中，候选人面临一个挑战：确定是否有两个字符串是彼此的旋转版本。具体来说，给定“s1”和“s2”，任务是通过旋转字符来验证“s1”是否是“s2”的修改版本。

面试官的方法

候选人的回答涉及找到“s2”中与“s1”中的子字符串匹配的最长前缀，该子字符串代表旋转点。通过将“s2”在该点划分为“s2a”和“s2b”，“s2a”和“s2b”的串联可以与“s1”进行比较以获得相等性。

更简单的解决方案

然而，面试官建议了更直接的方法：确保“s1”和“s2”具有相同的长度，然后测试“s2”是否是“s1”与其自身连接的子串。此方法利用了这样一个事实：旋转后的字符串与原始字符串连接时始终是原始字符串的子字符串。

Java 实现

在 Java 中，一个简单的实现该解决方案可能如下所示：

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

效率分析

该解决方案的时间复杂度为 O(n)，其中 n 是字符串的长度，因为它涉及单个字符串连接和对组合结果的子字符串搜索。由于连接字符串需要空间，空间复杂度也是 O(n)。

通过提供一种简单有效的方法来检查字符串旋转，这种替代方法满足了面试官对简单有效的要求检测字符串的旋转版本。

以上是如何高效判断两根弦是否互相旋转？的详细内容。更多信息请关注PHP中文网其他相关文章！