[LeetCode] 567. Permutation in String

문제

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1's permutations is the substring of s2.

567. Permutation in String는 문자열 s1과 s2가 주어졌을때 s2가 s1의 순열을 부분 문자열로 가지는지 판단하는 문제다.

여기서 문자는 영어 소문자로 이루어져 있다고 가정한다.

BCR(Best Conceivable Runtime)

s1과 s2의 모든 문자를 한 번씩은 확인해야 하기 때문에, BCR은 s1과 s2의 길이가 각각 $N$, $M$이라고 할 때 $O(N+M)$이다.

풀이 1

첫 번째로 생각할 수 있는 방법은 완전 탐색이다. s1의 모든 순열을 만들어가면서 s2가 이를 포함하는지 판단하는 방법이다. 해당 방법의 시간 복잡도는 $O(M*N!)$이기 때문에, 이 방법은 사용할 수 없다.

풀이 2

두 번째 방법은 s2을 선형 탐색하면서 s2[i]가 s1에 등장했던 문자의 경우 s2.substring(i, i+s1.length())가 s1의 순열인지 판단하는 방법이다.

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s2.length() < s1.length()) return false;
        int[] refCnts = getReferenceCounts(s1);
        for (int i = 0; i <= s2.length() - s1.length(); i++) {
            if (refCnts[s2.charAt(i)-'a'] > 0 && _checkInclusion(s1, s2, i)) {
                return true;
            }
        }
        return false;
    }

    public int[] getReferenceCounts(String s) {
        int[] refCnts = new int[26];
        for (int i = 0; i < s.length(); i++) {
            refCnts[s.charAt(i)-'a']++;
        }
        return refCnts;
    }

    public boolean _checkInclusion(String s1, String s2, int i) {
        int[] refCnts = getReferenceCounts(s1);
        for (int j = i; j < i+s1.length(); j++) {
            refCnts[s2.charAt(j)-'a'] --;
        }
        for (int j = 0; j < 26; j++) {
            if (refCnts[j] != 0) return false;
        }
        return true;
    }
}

이 방법은 s2[i]에 대해 $O(N)$이 걸리는 _checkInclusion()을 수행하고 있기 때문에, 시간 복잡도는 $O(M*N)$이다. 공간 복잡도는 문자의 등장 횟수를 저장하는 refCnts 배열을 사용하지만, 상수 길이의 refCnts를 최대 2개까지 생성하기 때문에 $O(1)$이다.

풀이 3

세 번째 방법은 두 번째 방법과 비슷하나 다음 탐색할 문자의 위치를 효율적으로 이동시킨다. _checkInclusion()이 다음 탐색할 문자의 위치를 반환하도록 수정했다. s2.substring(i, i+s1.length())를 검사할때, 이것이 s1의 순열이 아닌 경우에는 다음과 같은 경우가 존재한다.

• s1에 존재하지 않는 문자가 등장하는 경우
• s1에 존재하는 문자를 덜(또는 더 많이) 사용한 경우

s1에 존재하지 않는 문자가 등장하는 경우, 다음 탐색 위치를 이들 중 마지막에 등장하는 문자의 다음 위치로 이동시킨다. 왜냐하면, i부터 j까지 중 s1에 존재하지 않는 문자가 등장하기 때문에 s2.substring(i, j+1)은 절대로 s1의 순열이 될 수 없기 때문이다.

     public int _checkInclusion(String s1, String s2, int i) {
        int[] refCnts = getReferenceCounts(s1);
        for (int j = i+s1.length()-1; j >= i; j--) {
            // s1에 존재하지 않는 문자가 등장하는 경우
            if (refCnts[s2.charAt(j)-'a'] == 0) {
                return j+1;
            }
            refCnts[s2.charAt(j)-'a']--;
        }
        ...

s1에 존재하는 문자를 s2에서 덜(또는 더 많이) 사용한 경우 다음 탐색 위치를 해당 위치로 이동시킨다. 이는 s2.substring(j, j+s1.length())가 s1의 순열이 안될 가능성이 없기 때문이다.

        ...
        for (int j = i; j < i+s1.length(); j++) {
            // s1에 존재하는 문자를 s2에서 덜(또는 더 많이) 사용한 경우
            if (refCnts[s2.charAt(j)-'a'] > 0 || refCnts[s2.charAt(j)-'a'] < 0) {
                return j;
            }
        }
        return -1;
    }

전체적인 코드는 다음과 같다.

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s2.length() < s1.length()) return false;
        int[] refCnts = getReferenceCounts(s1);
        int i = 0;
        while (i <= s2.length()-s1.length()) {
            if (refCnts[s2.charAt(i)-'a'] > 0) {
                int ni = _checkInclusion(s1, s2, i);
                if (ni < 0) return true;
                i = ni;
            } else {
                i++;
            }
        }
        return false;
    }

    public int[] getReferenceCounts(String s) {
        int[] refCnts = new int[26];
        for (int i = 0; i < s.length(); i++) {
            refCnts[s.charAt(i)-'a']++;
        }
        return refCnts;
    }

    public int _checkInclusion(String s1, String s2, int i) {
        int[] refCnts = getReferenceCounts(s1);
        for (int j = i+s1.length()-1; j >= i; j--) {
            if (refCnts[s2.charAt(j)-'a'] == 0) {
                return j+1;
            }
            refCnts[s2.charAt(j)-'a']--;
        }
        for (int j = i; j < i+s1.length(); j++) {
            if (refCnts[s2.charAt(j)-'a'] > 0 || refCnts[s2.charAt(j)-'a'] < 0) {
                return j;
            }
        }
        return -1;
    }
}