← 전체 회차
A-018● Day 182026.05.20mediumleetcode #567neetcode150

문자열의 순열

#hash-table#two-pointers#string#sliding-window
↗ leetcode #567 · permutation-in-string
01

문제

· problem
P.018

문자열의 순열

↗ leetcode #567

두 문자열 s1과 s2가 주어질 때, s2가 s1의 순열을 부분문자열로 포함하면 true를, 그렇지 않으면 false를 반환하세요. 다시 말해, s1의 순열 중 하나가 s2의 부분문자열이면 true를 반환하세요.

제약
  • · 1 ≤ s1.length, s2.length ≤ 10⁴
  • · s1 and s2 consist of lowercase English letters
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
"ab"
"eidbaooo"
true
example 2input → output
"ab"
"eidboaoo"
false
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    순열(permutation)은 문자의 순서가 중요한가요?
  • ☐
    왜 두 개의 frequency 배열을 사용해야 하나요?
  • ☐
    matches 변수는 정확히 무엇을 세나요?
  • ☐
    왜 루프를 len(s1)부터 시작하나요?
  • ☐
    정렬을 사용하면 더 빠를까요?
  • ☐
    조기 종료 조건 if matches == 26이 반드시 필요한가요?
  • ☐
    만약 s1 = 'ab'이고 s2 = 'aba'라면, 결과는?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 길이 검사 - 불가능한 경우 제거
○
if len(s1) > len(s2):
○
if len(s1) >= len(s2):
○
if len(s1) < len(s2): return False
step 2· 빈도 배열 초기화 및 첫 윈도우 채우기
○
s1Count, s2Count = [0] * 26, [0] * 26
○
s1Count, s2Count = [0] * 25, [0] * 25
○
s1Count = [0] * 26  # s2Count는 없음
step 3· 초기 일치 횟수 계산│ 중첩
○
matches += 1 if s1Count[i] == s2Count[i] else 0
○
matches += 1 if s1Count[i] != s2Count[i] else 0
○
# 초기 matches 계산을 건너뜀
step 4· 슬라이딩 윈도우 메인 루프
○
for r in range(len(s1), len(s2)):
○
for r in range(len(s1)):
○
for r in range(len(s2)):
step 5· 오른쪽 끝 문자 추가 및 일치 횟수 업데이트│ 중첩
○
s2Count[index] += 1
○
s2Count[ord(s2[r]) - ord('a')] += 1
○
if s1Count[index] == s2Count[index] - 1:
    matches += 1
s2Count[index] += 1
step 6· 왼쪽 끝 문자 제거 및 일치 횟수 업데이트│ 중첩
○
s2Count[index] -= 1
○
s2Count[ord(s2[l]) - ord('a')] -= 1
l += 1
○
s2Count[ord(s2[l]) - ord('a')] -= 1
# l += 1이 없음
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
class Solution:
2
    def checkInclusion(self, s1: str, s2: str) -> bool:
3
        if len(s1) > len(s2):
4
            return False
5
6
        s1Count, s2Count = [0] * 26, [0] * 26
7
        for i in range(len(s1)):
8
            s1Count[ord(s1[i]) - ord("a")] += 1
9
            s2Count[ord(s2[i]) - ord("a")] += 1
10
11
        matches = 0
12
        for i in range(26):
13
            matches += 1 if s1Count[i] == s2Count[i] else 0
14
15
        l = 0
16
        for r in range(len(s1), len(s2)):
17
            if matches == 26:
18
                return True
19
20
            index = ord(s2[r]) - ord("a")
21
            s2Count[index] += 1
22
            if s1Count[index] == s2Count[index]:
23
                matches += 1
24
            elif s1Count[index] + 1 == s2Count[index]:
25
                matches -= 1
26
27
            index = ord(s2[l]) - ord("a")
28
            s2Count[index] -= 1
29
            if s1Count[index] == s2Count[index]:
30
                matches += 1
31
            elif s1Count[index] - 1 == s2Count[index]:
32
                matches -= 1
33
            l += 1
34
        return matches == 26
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
"ab"
"eidbaooo"
→
true
case 2
"ab"
"eidboaoo"
→
false
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.