[LeetCode] 567. Permutation in String

567. Permutation in String

Medium

 

 

 

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.

 

Example 1:

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

Example 2:

Input: s1 = "ab", s2 = "eidboaoo"
Output: false

 

Constraints:

• 1 <= s1.length, s2.length <= 104
• s1 and s2 consist of lowercase English letters.

---

문제 풀이

• s2문장에서 s1단어가 존재하는지 확인해야한다. 
• s1단어가 존재할 수 있다고 판단하는 상황은 연속적으로 붙어있으며 그 단어 크기 내의 글자의 순서는 상관없다. 
• 'acbd'에 'abc'가 존재한다. acb와 abc는 같은 크기와 같은 알파벳, 그리고 개수가 만족된다. 
• 'abcd'에 'abd'는 존재하지 않는다. 'abd'로 만들 수 있는 하나의 단어가 'abcd'안에서 만들어질 수 없기 때문이다.

슬라이딩 윈도우

• 문제의 제한 조건을 보면 10^4이므로 브루투 포스로 풀 수 있다. 
• 시간복잡도를 낮추기 위해 슬라이딩 윈도우를 사용한다.
• 찾을 단어 s1를 Counter를 이용하여 개수를 미리센다.
• s2 문장에서 단어를 하나씩 탐색하면서 s1 단어에 있는 알파벳인지 확인하고 카운터의 갯수를 하나씩 제거한다.
• 슬라이딩 윈도우이니 만큼 s1의 길이 즉 윈도우가 지나간 자리는 답을 체크할때 제거해줘야하기 때문에 카운터에서 1을 더한다.
• 매번 슬라이딩 윈도우 프로세스가 끝날때 마다 카운터의 모든 값이 0이면 정답 True를 리턴하고, 탐색을 모두 마친후에도 결과가 나오지 않는다면 False 를 리턴한다.

소스 코드

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        cntr, w = Counter(s1), len(s1)
        for i in range(len(s2)):
            if s2[i] in cntr:
                cntr[s2[i]] -= 1
            if i >= w and s2[i-w] in cntr:
                cntr[s2[i-w]] += 1
            
            if all([cntr[i] == 0 for i in cntr]):
                return True
        return False