[LeetCode] 796. Rotate String

문제

Given two strings s and goal, return true if and only if s can become goal after some number of shifts on s.

A shift on s consists of moving the leftmost character of s to the rightmost position.

For example, if s = "abcde", then it will be "bcdea" after one shift.

796. Rotate String는 문자열 s와 goal이 주어질때, s에 쉬프트 연산을 여러번 적용해서 goal을 만들 수 있는 것인지 판단하는 문제다.

BCR(Best Conceivable Runtime)

해당 조건을 만족하기 위해선 두 문자열의 길이가 같아야 한다. 또한 두 문자열을 한 번씩은 탐색해야기 때문에, s와 goal의 문자열의 길이가 $N$이라고 하면 BCR은 $O(2N)$.

풀이

본 문제는 다음과 같이, "s가 xy, 즉 접두사가 x이고 접미사가 y라고 할때 goal이 yx인가를 판단하시오." 라는 문제로 정리할 수 있다.

첫 번째로 생각한 방법은 s에 대해서 x와 y의 모든 경우에 대해 yx를 만든 뒤 goal과 동일한지 판단하는 방법이다.

class Solution {
    public boolean rotateString(String s, String goal) {
        if (s.length() != goal.length()) return false;
        for (int i = 0; i < s.length(); i++) {
            StringBuilder sb = new StringBuilder(s.substring(i, s.length()));
            sb.append(s.substring(0, i));
            if (sb.toString().equals(goal)) return true;
        }
        return false;
    }
}

x와 y의 경우의 수는 $N$이고, String.equals()의 시간 복잡도는 $O(N$)이므로 전체적인 시간 복잡도는 $O(N^2)$, 공간 복잡도는 $O(N)$이다.

두 번째 방법은 CTCI의 풀이인데, goal을 이어 붙여서 yxyx로 만든 뒤, s가 이에 속하는지 판단하는 방법이다.

class Solution {
    public boolean rotateString(String s, String goal) {
        if (s.length() != goal.length()) return false;
        StringBuilder sb = new StringBuilder(goal);
        for (int i = 0; i < goal.length(); i++) {
            sb.append(goal.charAt(i));
        }
        return sb.toString().contains(s);
    }
}

처음에 이를 보고 매우 창의적인 풀이라고 생각했다... 나는 왜 저 생각을 못했지? 이 방법의 시간 복잡도는 String.contains()에 의존하는데, 자바의 경우 String.contains()가 JDK 버젼에 따라 사용하는 알고리즘이 다르다고 한다. 보이어-무어(Boyer-Moore) 알고리즘을 용하면 최악의 경우 $O(N^2)$이 소요된다. KMP 알고리즘을 사용한다면 이를 $O(N)$으로 줄일 수 있다. 자바 API를 마구잡이로 사용하지 말고 어떤 알고리즘을 내부에서 사용하는지 공부할 필요가 있는 것 같다.