[DSA][Sliding Window] 03. Permutation in String

LeetCode 567

 

03. 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.

 

 

[질문하기]

- 문자열은 26개의 소문자 Character로만 이루어지나요? YES

 

 

[아이디어]

- Sliding window 기법과 26 크기의 배열을 사용하여 len(s1)만큼 check 하고 window를 한 칸씩 옮겨나가자. 

 

 

[풀이 1] Sliding Window

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2):
            return False

        countMap1 = [0] * 26
        countMap2 = [0] * 26

        for c in s1:
            countMap1[ord(c) - ord('a')] += 1

        window = len(s1)
        for i in range(window):
            countMap2[ord(s2[i]) - ord('a')] += 1

        for R in range(window, len(s2)):
            if countMap1 == countMap2:
                return True
            countMap2[ord(s2[R]) - ord('a')] += 1
            countMap2[ord(s2[R - window]) - ord('a')] -= 1

        return countMap1 == countMap2

이 문제를 처음 보면 "permutation" 조건 때문에 어렵다고 느낄 수 있다. 만약 permutation이 아니라 그냥 문자열을 비교하는 거였다면 어땠을까? 물론 s1 in s2 문법을 사용할 수도 있겠지만, 아래와 같은 방법으로 한 칸씩 옆으로 옮기면서 비교했을 것이다.

permutation도 똑같다. 다만 문자열 형태로 비교하는 것이 아니라, countMap 자체를 비교하면 된다.

문자열의 개수를 센 자료구조가 같은 형태를 띤다면, 그것이 곧 permutation이 같다는 의미이기 때문이다.

 

count map을 만들기 위해 hashMap 사용할 수도 있겠지만, 26개의 알파벳 소문자만 나올 것이기 때문에 26짜리 배열을 사용하여 O(1)의 공간 복잡도로 계산할 수 있다.

 

 

⏱️ 시간복잡도

문자열을 한 번 순회하기 때문에 O(n)의 시간 복잡도를 갖는다.

🧠 공간복잡도

countMap은 26 크기의 list이므로 O(1)의 공간 복잡도를 갖는다.