두 문자열이 서로 회전하는지 효율적으로 확인하는 방법은 무엇입니까?

문자열 회전 확인: 효율적인 솔루션

소프트웨어 개발자 직위에 대한 인터뷰에서 후보자에게 과제가 주어졌습니다. 문자열은 서로 회전된 버전입니다. 구체적으로 "s1"과 "s2"가 주어졌을 때 문자를 회전시켜 "s1"이 "s2"의 수정 버전인지 확인하는 작업이었습니다.

면접관의 접근 방식

지원자의 응답에는 회전 지점을 나타내는 "s1"의 하위 문자열과 일치하는 "s2"에서 가장 긴 접두어를 찾는 것이 포함되었습니다. 해당 지점에서 "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 중국어 웹사이트의 기타 관련 기사를 참조하세요!