[java] 면접 질문 : 한 문자열이 다른 문자열의 회전인지 확인

소프트웨어 개발자의 지위에 대한 인터뷰에서 내 친구가 오늘 다음과 같은 질문을 받았습니다.

두 개의 문자열을 감안 s1하고 s2어떻게되는지 확인한다 s1A는 회전 의 버전 s2?

예:

그렇다면 s1 = "stackoverflow"다음은 회전 된 버전 중 일부입니다.

"tackoverflows"
"ackoverflowst"
"overflowstack"

곳으로 "stackoverflwo"입니다 하지 회전 된 버전.

그가 준 대답은 다음과 같습니다.

s2하위 문자열 인 가장 긴 접두사를 가져 와서 s1회전 점을 찾습니다 . 당신이 그 지점을 찾으면, 휴식 s2그 시점에서 취득하는 s2a하고 s2b, 그럼 그냥 있는지 확인concatenate(s2a,s2b) == s1

나와 내 친구에게 좋은 해결책처럼 보입니다. 그러나 면접관은 다른 생각을했습니다. 그는 더 간단한 해결책을 요구했습니다. 이 작업을 수행하는 방법을 알려주십시오.Java/C/C++ 하시겠습니까?

미리 감사드립니다.

답변

먼저 확인 s1과 s2같은 길이입니다. 그런 다음 s2하위 문자열이 다음과 s1연결되어 있는지 확인하십시오 s1.

algorithm checkRotation(string s1, string s2)
  if( len(s1) != len(s2))
    return false
  if( substring(s2,concat(s1,s1))
    return true
  return false
end

자바에서 :

boolean isRotation(String s1,String s2) {
    return (s1.length() == s2.length()) && ((s1+s1).indexOf(s2) != -1);
}

답변

더 나은 대답은 “글쎄, 나는 stackoverflow 커뮤니티에 물어볼 것이고 아마도 5 분 안에 적어도 4 개의 정말로 좋은 답변을 얻을 것이다”라고 말할 것이다. 두뇌는 모두 훌륭하지만, 다른 사람들과 협력하여 솔루션을 얻는 방법을 알고있는 사람에게는 더 높은 가치를 부여합니다.

답변

또 다른 파이썬 예제 (The 답변을 기반으로) :

def isrotation(s1,s2):
     return len(s1)==len(s2) and s1 in 2*s2

답변

다른 사람들이 2 차 최악의 시간 복잡성 솔루션을 제출 했으므로 선형 솔루션을 추가합니다 ( KMP 알고리즘 기반 ).

bool is_rotation(const string& str1, const string& str2)
{
  if(str1.size()!=str2.size())
    return false;

  vector<size_t> prefixes(str1.size(), 0);
  for(size_t i=1, j=0; i<str1.size(); i++) {
    while(j>0 && str1[i]!=str1[j])
      j=prefixes[j-1];
    if(str1[i]==str1[j]) j++;
    prefixes[i]=j;
  }

  size_t i=0, j=0;
  for(; i<str2.size(); i++) {
    while(j>0 && str2[i]!=str1[j])
      j=prefixes[j-1];
    if(str2[i]==str1[j]) j++;
  }
  for(i=0; i<str2.size(); i++) {
    if(j>=str1.size()) return true;
    while(j>0 && str2[i]!=str1[j])
      j=prefixes[j-1];
    if(str2[i]==str1[j]) j++;
  }

  return false;
}

작업 예

답변

편집 : 당신이 그것을 발견하면 허용 된 대답은 이것보다 분명히 우아하고 효율적입니다. 원래 문자열을 두 배로 늘릴 생각이 없다면이 답변을 내가 한 일로 남겨 두었습니다.

난 그냥 그것을 무차별 강제합니다. 먼저 길이를 확인한 다음 가능한 모든 회전 오프셋을 시도하십시오. 그들 중 어느 것도 해결되지 않으면 거짓을 반환하십시오-그들 중 하나라도 있으면 즉시 true를 반환하십시오.

연결 할 필요가 없습니다. 포인터 (C) 또는 인덱스 (Java)를 사용하고 각 문자열마다 하나씩 따라 가십시오. 한 문자열의 시작 부분부터 시작하여 두 번째 문자열의 현재 후보 회전 오프셋을 시작하고 필요한 경우 줄 바꿈하십시오. . 문자열의 각 지점에서 문자가 같은지 확인하십시오. 첫 번째 문자열의 끝에 도달하면 완료된 것입니다.

적어도 자바에서는 아마도 연결하기가 쉬울 것입니다.

답변

다음은 재미를 위해 정규식을 사용하는 것입니다.

boolean isRotation(String s1, String s2) {
   return (s1.length() == s2.length()) && (s1 + s2).matches("(.*)(.*)\\2\\1");
}

두 문자열에 포함되지 않는 특수 구분 문자를 사용할 수 있으면 조금 더 간단하게 만들 수 있습니다.

boolean isRotation(String s1, String s2) {
   // neither string can contain "="
   return (s1 + "=" + s2).matches("(.*)(.*)=\\2\\1");
}

유한 반복과 함께 lookbehind를 대신 사용할 수도 있습니다.

boolean isRotation(String s1, String s2) {
   return (s1 + s2).matches(
      String.format("(.*)(.*)(?<=^.{%d})\\2\\1", s1.length())
   );
}

답변

우와, 우와 … 왜 모든 사람들이 O(n^2)답에 감격 합니까? 우리가 여기서 더 잘할 수 있다고 생각합니다. 위의 답변에는 루프 (substring / indexOf 호출) O(n)작업이 포함되어 O(n)있습니다. 보다 효율적인 검색 알고리즘으로도; 말을 Boyer-Moore하거나 KMP, 최악의 경우는 여전히O(n^2) 중복으로.

O(n)무작위 대답은 간단하다; Rabin 지문과 같은 해시를 사용하여O(1)슬라이딩 윈도우 . 해시 문자열 1, 해시 문자열 2, 그리고 문자열 주위로 해시 1의 창을 이동하고 해시 함수가 충돌하는지 확인하십시오.

최악의 경우가 “두 가닥의 DNA 스캔”과 같은 것으로 생각되면 충돌 가능성이 높아지고 아마도 O(n^(1+e))여기에서 추측 하는 것과 같은 것으로 저하 될 수 있습니다.

마지막으로 결정적인 O(nlogn)솔루션은 외부에서 매우 큰 상수를 갖습니다. 기본적으로 아이디어는 두 줄의 컨볼 루션을 취하는 것입니다. 컨벌루션의 최대 값은 회전 차이 (회전 한 경우)입니다. O(n)체크 확인한다. 좋은 점은 두 개의 동일한 최대 값이 있으면 둘 다 유효한 솔루션이라는 것입니다. 두 개의 FFT와 내적, iFFT로 컨볼 루션을 수행 할 수 있습니다 nlogn + nlogn + n + nlogn + n == O(nlogn).

0으로 채울 수 없으며 문자열의 길이가 2 ^ n임을 보장 할 수 없으므로 FFT는 빠른 것이 아닙니다. 그들은 여전히 느린 것입니다O(nlogn) 만 CT 알고리즘보다 훨씬 더 큰 상수입니다.

내가 말한 O(n)것은, 여기에 결정적 솔루션 이 있다고 100 % 긍정적 이지만, 그것을 찾을 수 있다면 감히.