如何高效判斷兩根弦是否互相旋轉？

檢查字串旋轉：一種有效的解決方案

在軟體開發人員職位的面試中，候選人面臨一個挑戰：確定是否有兩個字串是彼此的旋轉版本。具體來說，給定“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中文網其他相關文章！