Permutation in String
문자열의 순열은 원래 문자열과 같은 횟수만큼 각 문자를 사용해 순서를 바꾼 것입니다. tar, rat, art는 서로 순열 관계입니다. 소문자 영어 문자로 이루어진 두 문자열 s1과 s2가 주어집니다. s1의 어떤 순열이 부분 문자열(연속된 문자들의 나열)로 s2에 나타나면 true를 반환하고, 그렇지 않으면 false를 반환하세요.
함수
- s1string
- 재배열할 글자
- s2string
- 검색할 문자열
- 반환값boolean
- s2의 부분 문자열이 s1을 재배열한 결과이면 true
제약 조건
1 ≤ s1.length ≤ 2 × 1041 ≤ s2.length ≤ 5 × 104s1과s2에는 소문자 영문자(a부터z까지)만 포함되어 있습니다.s1은s2보다 더 길 수 있습니다.
예제
- 입력
- s1 = "tar"s2 = "smartphone"
- 출력
- true
- 설명
smartphone의 인덱스 2부터 4까지의 부분 문자열art에는tar와 같은 문자, 즉a하나,r하나,t하나가 들어 있습니다.
- 입력
- s1 = "noon"s2 = "onion"
- 출력
- false
- 설명
- 길이가 4인 부분 문자열은
onio와nion입니다.noon에는n두 개와o두 개가 필요하지만, 각 구간에는 그중 하나 대신i가 들어 있습니다.noon의 모든 문자가onion에 나타나지만, 어떤 구간도 각 문자의 개수가 맞지 않습니다.
- 입력
- s1 = "abcd"s2 = "dcb"
- 출력
- false
- 설명
abcd의 어떤 순열이든 글자가 4개이고,dcb에는 3개뿐이므로dcb를 포함할 수 없습니다.
제출 시 숨은 테스트 +17개
후속 질문
s1의 순열이 시작하는 모든 s2의 인덱스를 여전히 O(m + n) 시간에 반환할 수 있나요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
순열에서는 문자의 순서가 중요하지 않습니다.
s2의 부분 문자열이s1의 순열인지 여부를 결정하는 것은 무엇이며, 그 부분 문자열의 길이는 얼마여야 할까요?길이가
m = s1.length인 부분 문자열만 조건을 만족할 수 있으며, 그러한 부분 문자열은 26개 문자의 개수가s1의 개수와 같을 때에만s1의 순열입니다.m길이의 윈도우를s2위로 이동합니다. 매 단계마다 오른쪽에 문자 하나를 추가하고 왼쪽에 있는 문자 하나를 제거하므로, 다시 세는 대신 윈도우의 개수를 하나는 +1, 하나는 -1로 갱신한 다음s1의 개수와 비교합니다.
풀이
s1의 순열을 나열하는 것은 가망이 없습니다. 글자 10개만으로도 순서가 3,628,800가지나 됩니다. 해결 방법은 순서를 고려하지 않는 것입니다. s2의 부분 문자열이 s1의 순열이 되는 조건은 길이 m이 같고 각 글자의 개수도 모두 같은 것입니다. 따라서 모든 후보는 길이가 동일한 고정된 윈도우이며, 매 단계마다 글자 하나를 추가하고 하나를 제거해 글자 개수를 갱신하면서 s2를 따라 윈도우 하나를 슬라이드하면 됩니다.
모든 창을 처음부터 세세요
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
s1의 모든 순열을 만들어 하나씩 찾아보는 직접적인 방법은 20개의 문자만으로도 순서가 2 × 10^18개를 넘어 곧바로 불가능해집니다. 대신 질문을 거꾸로 생각해 보세요. s2의 부분 문자열이 s1의 순열이 되려면 문자가 정확히 m개이고, 각 문자가 s1에서와 같은 횟수만큼 사용되어야 합니다. 부분 문자열 안의 순서는 중요하지 않습니다.
그러므로 먼저 26개의 숫자로 된 표에 s1의 문자 개수를 세어 둡니다. 인덱스 0은 a, 25는 z입니다. 그런 다음 s2에서 길이가 m인 모든 부분 문자열을 하나씩 살펴보며 새 표에 문자를 세고, 두 표를 비교합니다. smartphone에서 tar를 찾는다면, 각 구간은 sma, mar, art 등이고, art가 일치합니다. a, r, t가 각각 하나씩 있습니다.
모든 후보를 살펴보므로 이 방법은 정확합니다. 하지만 이웃한 구간은 m-1개의 문자를 공유하는데도 그 문자를 모두 다시 세므로 느립니다. m = 15,000이고 n = 50,000이면 길이가 15,000인 구간이 35,001개이며, 약 5 × 10^8번의 연산이 필요합니다.
알고리즘
s1이s2보다 길면false를 반환합니다.- 0이 26개 들어 있는
need테이블에s1의 각 문자를 셉니다. - 0부터 n-m까지의 모든 시작 인덱스에 대해, 해당 시작 위치부터
m개의 문자를 새로운 테이블에 셉니다. - 그 테이블이
need와 같으면true를 반환합니다. - 마지막 윈도우를 확인한 뒤
false를 반환합니다.
def checkInclusion(s1, s2):
m, n = len(s1), len(s2)
if m > n:
return False
need = [0] * 26 # need[0] is 'a', need[25] is 'z'
for ch in s1:
need[ord(ch) - 97] += 1
for start in range(n - m + 1):
# Count the letters of s2[start : start + m] from scratch
window = [0] * 26
for i in range(start, start + m):
window[ord(s2[i]) - 97] += 1
if window == need:
return True
return False창을 움직여 26개의 개수를 비교하세요
핵심 아이디어
서로 이웃한 두 윈도우는 문자 두 개만 다릅니다. mar에서 art로 이동하면 왼쪽에서 m이 빠지고 오른쪽에 t가 추가됩니다. 따라서 매번 m개의 문자를 다시 세는 대신 현재 윈도우의 테이블 하나를 유지하고, 한 단계마다 +1과 -1을 한 번씩 적용해 변경하면 됩니다.
s1로 need를 채우고, s2의 처음 m개 문자로 window를 채운 뒤 두 테이블을 비교합니다. 그런 다음 m부터 n-1까지 모든 i에 대해 s2[i]를 더하고 s2[i-m]를 제거한 뒤 다시 비교합니다. 이제 윈도우는 s2[i-m+1..i]이며, 여전히 길이는 m입니다.
각 단계에는 두 번의 갱신과 숫자 26개의 비교가 필요하며, m의 값과는 관계없습니다. 가장 큰 입력에서도 연산량은 약 26 × 50,000 = 1.3 × 10^6회로, s2의 길이에 선형적으로 비례합니다. 대부분의 면접관이 기대하는 풀이입니다.
알고리즘
s1이s2보다 길면false를 반환합니다.s1의 문자를need에 세고,s2의 처음m개 문자를window에 셉니다.- 두 테이블이 같으면
true를 반환합니다. m부터n-1까지 각i에 대해s2[i]의 개수를 1 늘리고,s2[i-m]의 개수를 1 줄입니다. 두 테이블이 같으면true를 반환합니다.false를 반환합니다.
def checkInclusion(s1, s2):
m, n = len(s1), len(s2)
if m > n:
return False
need = [0] * 26
window = [0] * 26
for i in range(m):
need[ord(s1[i]) - 97] += 1
window[ord(s2[i]) - 97] += 1 # the first window is s2[0 : m]
if window == need:
return True
for i in range(m, n):
window[ord(s2[i]) - 97] += 1 # s2[i] enters on the right
window[ord(s2[i - m]) - 97] -= 1 # s2[i - m] leaves on the left
if window == need:
return True
return False창을 이동하고 균형이 맞지 않는 문자를 추적하세요
핵심 아이디어
매 단계에서 26개의 숫자를 비교하면 불필요한 작업이 반복됩니다. 한 단계에서 바뀌는 숫자는 두 개뿐이기 때문입니다. 대신 balance 테이블 하나를 유지하세요. balance[c]는 s1에 있는 문자 c의 개수에서 현재 윈도우에 있는 개수를 뺀 값입니다. 모든 26개의 잔액이 0일 때만 윈도우는 s1의 순열입니다. 테이블과 함께 잔액이 0이 아닌 문자의 개수인 unbalanced도 유지하고, 이 값이 0이 되는 순간 true를 반환하세요.
기록 관리에는 한 가지 규칙이 있습니다. balance[c]를 바꾸기 전에 값이 0이라면, 해당 문자의 균형이 깨지려는 것이므로 unbalanced에 1을 더하세요. 값을 바꾼 뒤 0이라면, 해당 문자의 균형이 맞은 것이므로 1을 빼세요. 문자가 윈도우에 들어오면 잔액이 1 감소하고, 윈도우에서 나가면 잔액이 1 증가합니다. 잔액이 2에서 1로 바뀌는 경우에는 어느 확인 조건도 충족하지 않습니다. 맞습니다. 해당 문자는 균형이 맞지 않았고, 여전히 맞지 않기 때문입니다.
tar와 smartphone을 따라가 보세요. 처음 잔액은 a: 1, r: 1, t: 1이므로 unbalanced는 3입니다. s와 m이 들어와 값은 5가 되고, 이어서 a가 들어와 a의 잔액이 0이 되면서 값은 4가 됩니다. r이 들어와 값은 3이 되고, 동시에 s가 나가면서 값은 2가 됩니다. t가 들어와 값은 1이 되고, 동시에 m이 나가면서 값은 0이 됩니다. 이때 윈도우 art가 답입니다.
첫 문자부터 unbalanced == 0인지 확인해도 됩니다. 윈도우에 m개보다 적은 문자가 있는 동안에는 잔액의 합이 양수이므로, 적어도 하나는 0이 아닙니다. 각 단계에서 일정한 양의 작업만 수행하므로 전체 탐색의 시간 복잡도는 O(m + n)이고, 테이블에는 항상 숫자 26개만 들어 있으므로 공간 복잡도는 O(1)입니다.
알고리즘
s1이s2보다 길면false를 반환합니다.s1을balance에 반영하고, 균형이 0이 아닌 문자의 개수를unbalanced에 설정합니다.s2의 각 인덱스i에 대해s2[i]의 균형에서 1을 빼고, 해당 균형이 0이었다면unbalanced에 1을 더하며 0이 되었다면 1을 뺍니다.i ≥ m이면 같은 방식으로 기록하면서s2[i-m]의 균형에 1을 더합니다.unbalanced가 0이면true를 반환합니다. 반복문이 끝난 후false를 반환합니다.
def checkInclusion(s1, s2):
m, n = len(s1), len(s2)
if m > n:
return False
# balance[c]: copies of letter c in s1 minus copies in the window
balance = [0] * 26
for ch in s1:
balance[ord(ch) - 97] += 1
unbalanced = sum(1 for b in balance if b != 0)
for i in range(n):
# s2[i] enters the window on the right
c = ord(s2[i]) - 97
if balance[c] == 0:
unbalanced += 1
balance[c] -= 1
if balance[c] == 0:
unbalanced -= 1
# s2[i - m] leaves on the left once the window would pass m letters
if i >= m:
c = ord(s2[i - m]) - 97
if balance[c] == 0:
unbalanced += 1
balance[c] += 1
if balance[c] == 0:
unbalanced -= 1
if unbalanced == 0:
return True
return False
함정과 경계 사례
대부분의 오답은 윈도우의 경계에서 발생하거나, 각 문자가 몇 번 나오는지가 아니라 어떤 문자가 나오는지만 확인할 때 발생합니다.
s1의 모든 문자가 윈도우에 있는지만 확인하는 경우.onio에는noon의 모든 문자가 있지만,noon의 순열은 아닙니다. 개수를 비교하세요.- 잘못된 문자를 제거하는 경우.
s2[i]가 들어오면 나가는 문자는s2[i-m]이므로, 윈도우는s2[i-m+1..i]가 됩니다.s2[i-m+1]을 제거하면 윈도우에는m-1개의 문자만 남습니다. - 첫 번째 윈도우를 건너뛰는 경우. 슬라이딩한 후에만 비교하면 인덱스 0에 있는 순열을 절대 찾지 못합니다.
s1이s2보다 긴 경우를 잊는 것. Rust에서는 부호 없는 길이에n - m을 계산하면 언더플로가 발생하고, Swift에서는0...(n - m)범위에서 오류가 발생합니다. 먼저false를 반환하세요.- 참조를 비교하는 언어에서
==로 배열을 비교하는 경우. JavaScript와 Dart에서는 서로 다른 두 배열이 절대==가 아니며, Java에서는Arrays.equals를 사용하세요.
자주 묻는 질문4
Permutation in String의 시간 복잡도는 얼마인가요?
슬라이딩 윈도우를 사용하면 O(m + n)이고, 여기서 m은 s1의 길이이며 n은 s2의 길이입니다. s1은 한 번 세고, s2의 각 문자는 윈도우에 한 번 들어왔다가 한 번 나갑니다. 반면 매 윈도우를 처음부터 다시 세면 O(n · m)의 비용이 듭니다.
문자열 안에서 순열을 찾는 것은 문자열 안에서 애너그램을 찾는 것과 같은가요?
그렇습니다. s1의 순열은 s1의 애너그램이므로, s2에서 길이가 m인 부분 문자열 중 s1의 애너그램이 되는 것이 있는지가 핵심입니다. 두 문자열 전체의 애너그램 여부를 확인할 때는 문자 개수를 한 번 비교합니다. 여기서는 같은 비교를 s2를 따라 이동하는 윈도우에 적용합니다.
여기서 슬라이딩 윈도우의 크기는 왜 고정되어 있나요?
s1의 모든 순열은 정확히 m개의 문자를 가지므로 길이가 m인 윈도우만 일치할 수 있습니다. 중복 문자가 없는 가장 긴 부분 문자열과 같은 문제에서는 윈도우를 늘리거나 줄이지만, 여기서는 양쪽 끝이 한 번에 한 단계씩 함께 이동합니다.
26개의 카운터 배열 대신 해시 맵을 사용해도 되나요?
네, 문자열에 어떤 문자든 포함될 수 있다면 맵이 필요합니다. 소문자만 있다면 크기가 26인 배열이 더 빠르고 상수 공간을 사용합니다. 맵을 사용할 때는 두 맵에 같은 문자가 있으면 서로 같다고 판단되도록 개수가 0으로 줄어든 키를 삭제하거나, 이전 접근 방식의 unbalanced 카운터를 사용하면 됩니다. 맵에서도 같은 방식으로 작동합니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
Python
def checkInclusion(s1, s2):
# 여기에 코드를 작성하세요케이스 1
케이스 2
케이스 3
입력
s1 = "tar" s2 = "smartphone"
기대값
true