[코딩인터뷰 완전정복] 1.9 문자열 회전

Q : 한단어가 다른 문자열에 포함되어 있는지 판별하는 isSubstring 이라는 메서드가 있다고 하자.

s1과 s2의 두 문자열이 주어졌을때 s1이 s2의 회전인지 판별하고자 한다.

isSubstring을 1번만 호출해서 판별할 수 있는 코드를 작성하라.

 

회전 : abcde → cdeab

 

s1을 문자열 xy로 나눴을때 yx는 s1의 회전이다.

단순하게 생각해보면 y가 s2의 처음에 나오는지 확인하고 그 뒤가 x와 일치하는지 확인하면 되지만

이 방법은 isSubstring을 1번만 호출하라는 지시에 맞지 않다.

bool isRotate(string s1, string s2){
    return isSubstring(s1+s1, s2);
}

 

조금 더 생각을 해보자.

s1 = xy , s2 = yx

라고 한다면 xyxy는 반드시 yx를 부분 문자열로 가지게 된다.

따라서 s1+s1이 s2를 부분 문자열로 가지는지만 확인하면 s2가 s1의 회전인지 알 수 있다.