Bagaimana untuk menentukan dengan cekap jika dua rentetan adalah putaran antara satu sama lain?

Menyemak Putaran Rentetan: Penyelesaian yang Cekap

Dalam temu bual untuk jawatan pembangun perisian, seorang calon telah dikemukakan cabaran: tentukan sama ada dua rentetan adalah versi diputar antara satu sama lain. Khususnya, diberi "s1" dan "s2," tugasnya adalah untuk mengesahkan sama ada "s1" ialah versi "s2" yang diubah suai dengan memutarkan aksaranya.

Pendekatan Penemuduga

Respons calon melibatkan mencari awalan terpanjang dalam "s2" yang sepadan dengan subrentetan dalam "s1," yang akan mewakili titik putaran. Dengan membahagikan "s2" pada titik itu kepada "s2a" dan "s2b," gabungan "s2a" dan "s2b" boleh dibandingkan dengan "s1" untuk kesaksamaan.

Penyelesaian Lebih Ringkas

Walau bagaimanapun, penemuduga mencadangkan pendekatan yang lebih langsung: memastikan bahawa "s1" dan "s2" mempunyai panjang yang sama dan kemudian menguji jika "s2" ialah subrentetan "s1" yang digabungkan dengan dirinya sendiri. Kaedah ini memanfaatkan fakta bahawa rentetan yang diputar akan sentiasa menjadi subrentetan daripada rentetan asal apabila digabungkan dengannya.

Pelaksanaan Java

Di Java, pelaksanaan mudah bagi penyelesaian ini mungkin kelihatan seperti:

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

Analisis Kecekapan

Kerumitan masa penyelesaian ini ialah O(n), dengan n ialah panjang rentetan, kerana ia melibatkan gabungan rentetan tunggal dan carian subrentetan pada hasil gabungan. Kerumitan ruang adalah O(n) juga, disebabkan oleh ruang yang diperlukan untuk rentetan bercantum.

Dengan menyediakan kaedah yang mudah dan cekap untuk menyemak putaran rentetan, pendekatan alternatif ini memenuhi permintaan penemu duga untuk kesederhanaan dan berkesan mengesan versi rentetan yang diputar.

Atas ialah kandungan terperinci Bagaimana untuk menentukan dengan cekap jika dua rentetan adalah putaran antara satu sama lain?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!