Is Subsequence

Q: Is Subsequence의 시간 복잡도는 얼마인가요?

두 포인터 솔루션은 n 과 m 이 각각 s 와 t 의 길이일 때 O(n + m) 시간에 실행되며, 추가 메모리로 O(1) 을 사용합니다. 실제로는 루프가 최대 m 단계 후에 종료됩니다. 접두사 테이블에는 O(n × m) 시간이 걸립니다.

Q: Is Subsequence에서 그리디 투 포인터 접근 방식은 왜 작동할까요?

s 의 문자를 t 에서 가능한 한 가장 앞선 위치에 맞추면 나머지 문자들이 사용할 수 있는 t 의 나머지 부분이 가장 길어집니다. 더 뒤에 있는 문자를 사용하는 배치는 순서를 깨뜨리지 않고 더 앞에 있는 문자로 바꿀 수 있으므로, 가능한 배치가 있다면 그리디 방식으로 찾을 수 있습니다.

Q: 같은 t에 대해 여러 문자열을 빠르게 확인하려면 어떻게 해야 하나요?

t 를 한 번 준비하세요. 각 문자에 대해 해당 문자가 나타나는 인덱스를 정렬된 목록으로 저장합니다. s[i] 를 배치하려면 해당 문자의 목록에서 이전 일치 항목보다 큰 첫 번째 인덱스를 이진 탐색합니다. 그러면 각 검사에 드는 비용이 O(m) 대신 O(n log m) 이 됩니다.

Q: 부분 수열과 부분 문자열의 차이는 무엇인가요?

부분 문자열은 연속된 글자들의 묶음이고, 부분 수열은 순서만 유지된다면 글자를 건너뛸 수 있습니다. ace 는 abcde 의 부분 수열이지만 부분 문자열은 아닙니다. 모든 부분 문자열은 부분 수열이지만, 그 반대는 성립하지 않습니다.

쉬움투 포인터

+10

두 문자열 s와 t가 주어집니다. 남은 문자의 순서를 유지하면서 t에서 일부 문자(없을 수도 있음)를 삭제해 s로 만들 수 있으면 true를 반환하고, 그렇지 않으면 false를 반환하세요. 예를 들어, ace는 abcde의 부분 수열이지만 aec는 그렇지 않습니다.

함수

isSubsequence(s: string, t: string) → boolean

sstring: 찾을 문자열
tstring: 문자를 삭제할 문자열
반환값boolean: 간격이 있어도 s를 t 안에서 순서대로 읽을 수 있다면 true

제약 조건

1 ≤ s.length ≤ 3 × 10⁴
1 ≤ t.length ≤ 5 × 10⁴
s와 t에는 소문자 영어 알파벳만 포함되어 있습니다.

예제

입력: s = "ace"t = "abcde"
출력: true
설명: abcde에서 b와 d를 삭제하면 같은 순서로 ace가 남습니다.

입력: s = "aec"t = "abcde"
출력: false
설명: t에는 세 글자가 모두 있지만, 유일한 c는 유일한 e 앞에 있습니다. 인덱스 4에 있는 e를 사용하고 나면, 그 오른쪽에는 c가 남아 있지 않습니다.

입력: s = "moon"t = "monsoon"
출력: true
설명: monsoon의 인덱스 0에 있는 m, 인덱스 1과 4에 있는 o, 인덱스 6에 있는 n을 사용하세요. 그 사이의 문자는 삭제됩니다.

제출 시 숨은 테스트 +20개

후속 질문

t가 그대로 있고 서로 다른 문자열 s 백만 개를 t와 비교해야 한다고 가정해 보세요. 매번 t 전체를 다시 읽는 것보다 각 비교를 더 빠르게 하려면 t를 어떻게 준비하면 좋을까요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

부분 수열은 t의 어느 위치에서든 문자를 건너뛸 수 있으므로, s를 t 안에 배치하는 여러 방법을 시도해야 할 것처럼 보일 수 있습니다. 하지만 그럴 필요는 없습니다. s의 각 문자를 배치할 수 있는 가장 이른 위치에서 일치시키는 것은 다른 어떤 선택보다 나쁘지 않으며, 이렇게 하면 두 개의 포인터를 사용해 왼쪽에서 오른쪽으로 한 번만 탐색하면 됩니다.

접두사에 대한 동적 프로그래밍

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

더 작은 질문을 해 보세요. s의 처음 i개 문자가 t의 처음 j개 문자 안에 들어갈까요? 그 답을 dp[i][j]라고 합시다. t[:j-1] 안에 들어간다면 t[j-1]을 삭제할 수 있으므로 t[:j] 안에도 들어갑니다. s[i-1]이 t[j-1]과 같다면 그 문자도 사용할 수 있으며, 그러려면 s의 처음 i-1개 문자가 t[:j-1] 안에 들어가야 합니다. 따라서 dp[i][j] = dp[i][j-1] or (s[i-1] == t[j-1] and dp[i-1][j-1])이고, s의 빈 접두사는 어디에나 들어갑니다.

행 i는 행 i-1만 읽으므로 길이가 m+1인 두 행이면 충분합니다. 답은 마지막 행의 마지막 셀입니다.

이것은 최장 공통 부분 수열을 구할 때 만드는 것과 같은 표이며, 올바른 방법이지만 모든 셀을 채웁니다. s가 25,000자이고 t가 50,000자라면 셀이 1.25 × 10^9개나 되는데, 이는 두 문자열을 한 번씩만 훑는 데 필요한 양보다 훨씬 많습니다.

알고리즘

모든 값이 true인 m+1개의 값으로 이루어진 행 prev를 만듭니다. 빈 s는 t의 모든 접두사에 들어맞습니다.
1부터 n까지 각 i에 대해 cur[0] = false인 행 cur를 만듭니다.
1부터 m까지 각 j에 대해 cur[j]를 cur[j-1]로 설정하거나, s[i-1]이 t[j-1]과 같을 때는 prev[j-1]로 설정합니다.
prev를 cur로 바꿉니다.
prev[m]을 반환합니다.

def isSubsequence(s, t):
    n, m = len(s), len(t)
    # prev[j]: the first i-1 letters of s fit inside t[:j]. An empty s fits anywhere.
    prev = [True] * (m + 1)
    for i in range(1, n + 1):
        cur = [False] * (m + 1)
        for j in range(1, m + 1):
            cur[j] = cur[j - 1] or (s[i - 1] == t[j - 1] and prev[j - 1])
        prev = cur
    return prev[m]

그리디 매칭을 사용하는 두 포인터

핵심 아이디어

t를 왼쪽에서 오른쪽으로 읽으면서, 아직 필요한 s의 다음 문자를 가리키는 포인터 i를 유지하세요. t[j]가 s[i]와 같으면 해당 문자를 사용하고 i를 앞으로 이동하세요. 어느 경우든 j를 앞으로 이동하세요. i가 s의 끝에 도달하면 모든 문자가 순서대로 들어갈 자리를 찾은 것입니다.

첫 번째로 일치하는 문자를 선택해도 괜찮은 이유는 무엇일까요? 유효한 배치에서 s[i]의 더 뒤에 있는 복사본을 사용한다고 가정해 보세요. 그 문자를 가장 먼저 나오는 복사본으로 바꾸어도 순서는 유지되고, 나머지 s를 위해 t에서 오른쪽에 남겨 두는 부분이 더 많아집니다. 따라서 탐욕적 선택은 존재하는 배치를 놓치는 일이 없습니다. moon을 monsoon에서 찾을 때 포인터는 인덱스 1의 o를 선택하고, n과 s를 건너뛴 다음, 인덱스 4의 o를 선택하고 인덱스 6의 n에서 끝납니다.

j는 t의 각 문자를 한 번씩 방문하고 i는 앞으로만 이동하므로, 루프는 최대 m번 실행됩니다. 필요한 메모리는 인덱스 두 개뿐입니다.

알고리즘

s에 대해 i = 0으로, t에 대해 j = 0으로 설정합니다.
두 인덱스가 모두 각 문자열의 범위 안에 있는 동안 s[i]와 t[j]를 비교합니다.
두 값이 같으면 i를 증가시킵니다.
모든 경우에 j를 증가시킵니다.
i가 s의 길이와 같은지 반환합니다.

def isSubsequence(s, t):
    i = j = 0
    while i < len(s) and j < len(t):
        if s[i] == t[j]:
            i += 1
        j += 1
    return i == len(s)

함정과 경계 사례

두 포인터 루프는 짧고, 버그는 경계에서 발생합니다.

각 s 문자를 이전에 일치한 위치 다음이 아니라 t의 아무 위치에서나 찾는 것. 이렇게 하면 순서가 어긋난 abcde에서 aec도 허용됩니다.
문자 하나를 두 번 사용하는 것. noon은 moon의 부분 수열이 아닙니다. moon에는 인덱스 3에 n이 하나만 있으며, 이 문자를 noon의 첫 글자와 마지막 글자로 동시에 사용할 수 없습니다.
j가 t의 끝에 도달했는지를 반환하는 것. s를 찾았는지와 관계없이 루프가 그 지점에서 끝나는 경우가 많습니다. 이를 알려주는 것은 i뿐입니다.
s가 t보다 길 수 있다는 점을 잊는 것. ab에 대한 abc는 false를 반환해야 하며, t의 문자가 모두 소진될 때 루프를 멈추면 그렇게 됩니다.
i가 s의 끝에 도달한 뒤 s[i]를 읽는 것. Python이나 Java에서는 해당 읽기에서 예외가 발생하므로, 비교하기 전에 i를 확인하세요.

자주 묻는 질문4

Is Subsequence의 시간 복잡도는 얼마인가요?

두 포인터 솔루션은 n과 m이 각각 s와 t의 길이일 때 O(n + m) 시간에 실행되며, 추가 메모리로 O(1)을 사용합니다. 실제로는 루프가 최대 m단계 후에 종료됩니다. 접두사 테이블에는 O(n × m) 시간이 걸립니다.

Is Subsequence에서 그리디 투 포인터 접근 방식은 왜 작동할까요?

s의 문자를 t에서 가능한 한 가장 앞선 위치에 맞추면 나머지 문자들이 사용할 수 있는 t의 나머지 부분이 가장 길어집니다. 더 뒤에 있는 문자를 사용하는 배치는 순서를 깨뜨리지 않고 더 앞에 있는 문자로 바꿀 수 있으므로, 가능한 배치가 있다면 그리디 방식으로 찾을 수 있습니다.

같은 t에 대해 여러 문자열을 빠르게 확인하려면 어떻게 해야 하나요?

t를 한 번 준비하세요. 각 문자에 대해 해당 문자가 나타나는 인덱스를 정렬된 목록으로 저장합니다. s[i]를 배치하려면 해당 문자의 목록에서 이전 일치 항목보다 큰 첫 번째 인덱스를 이진 탐색합니다. 그러면 각 검사에 드는 비용이 O(m) 대신 O(n log m)이 됩니다.

부분 수열과 부분 문자열의 차이는 무엇인가요?

부분 문자열은 연속된 글자들의 묶음이고, 부분 수열은 순서만 유지된다면 글자를 건너뛸 수 있습니다. ace는 abcde의 부분 수열이지만 부분 문자열은 아닙니다. 모든 부분 문자열은 부분 수열이지만, 그 반대는 성립하지 않습니다.

Python

def isSubsequence(s, t):
    # 여기에 코드를 작성하세요

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

s = "ace"
t = "abcde"

기대값

true