Is Subsequence

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

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

Q: Is Subsequence는 최장 공통 부분 수열과 어떤 관련이 있나요?

s 는 두 문자열의 최장 공통 부분 수열의 길이가 n , 즉 s 의 전체 길이일 때 정확히 t 의 부분 수열입니다. 첫 번째 접근법의 접두사 테이블은 그 문제를 위해 만드는 것입니다. 여기서는 s 전체가 들어맞는지만 알면 되므로 탐욕적으로 한 번 훑는 것으로 충분합니다.

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

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

쉬움투 포인터

+10

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

함수

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

sstring: 찾을 문자열
tstring: 문자를 삭제할 문자열
반환값boolean: t 안에서 s를 순서대로 읽을 수 있다면 참이며, 중간에 간격이 있을 수 있습니다

제약 조건

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을 사용합니다. 그 사이의 글자들은 삭제됩니다.

후속 질문

t를 고정해 두고 백만 개의 문자열 s를 대상으로 확인한다면, 각 확인이 t 전체를 읽는 것보다 빠르도록 t를 어떻게 준비할 수 있을까요?

힌트

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

3개 중 0개 열림

풀이

부분 수열은 t의 어느 위치에서든 글자를 건너뛸 수 있으므로, s를 여러 방식으로 배치해 보는 것이 좋을 것처럼 보입니다. 하지만 그럴 필요는 없습니다. s의 각 글자를 들어갈 수 있는 가장 이른 위치에 맞추는 것이 다른 어떤 선택보다 나쁠 수는 없으므로, 두 포인터를 사용해 왼쪽에서 오른쪽으로 한 번만 훑으면 판별할 수 있습니다.

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

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

핵심 아이디어

dp[i][j]가 s의 처음 i개 문자가 t의 처음 j개 문자 안에 들어가는지를 나타낸다고 하자. t[j-1]를 사용하지 않고도 이미 들어가거나, s[i-1]와 t[j-1]가 같고 처음 i-1개 문자가 t[:j-1] 안에 들어가면 들어간다. 빈 접두사는 어디에나 들어가며, 행 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]

그리디 매칭을 이용한 투 포인터

핵심 아이디어

필요한 s의 다음 문자를 가리키는 포인터 i를 유지하고, t에서 처음 만나는 해당 문자를 선택합니다. 이 선택은 안전합니다. 유효한 배치에서 s[i]의 더 뒤에 있는 문자를 사용하더라도, 가장 먼저 나오는 문자를 대신 선택하면 순서가 유지되고 나머지 s에 사용할 t의 부분이 더 많이 남습니다. 따라서 배치가 하나라도 존재한다면 탐욕적 방법으로 찾을 수 있습니다.

루프는 t의 각 문자를 최대 한 번 읽고 인덱스 두 개를 유지합니다. 시간 복잡도는 O(n + m)이고 메모리 복잡도는 O(1)입니다.

알고리즘

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)

함정과 경계 사례

이전 일치 항목 다음이 아니라 t의 어디에서든 s의 각 문자를 찾는 것. 이렇게 하면 abcde에서 aec를 받아들이게 됩니다.
문자 하나를 두 번 사용하는 것. noon은 moon의 부분 수열이 아닙니다. 인덱스 3에 있는 유일한 n은 첫 번째 문자와 마지막 문자를 동시에 나타낼 수 없습니다.
j가 t의 끝에 도달했는지를 반환하는 것. s를 찾았는지와 관계없이 루프가 그 지점에서 끝나는 경우가 많습니다. 이를 알려 주는 것은 i뿐입니다.
t의 문자가 모두 소진되어도 멈추지 않는 것. ab를 대상으로 abc를 확인하면 false를 반환해야 합니다.
i가 s의 끝에 도달한 뒤 s[i]를 읽는 것. Python이나 Java에서는 읽기 작업에서 예외가 발생하므로 비교하기 전에 i를 확인하세요.

자주 묻는 질문3

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

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

Is Subsequence는 최장 공통 부분 수열과 어떤 관련이 있나요?

s는 두 문자열의 최장 공통 부분 수열의 길이가 n, 즉 s의 전체 길이일 때 정확히 t의 부분 수열입니다. 첫 번째 접근법의 접두사 테이블은 그 문제를 위해 만드는 것입니다. 여기서는 s 전체가 들어맞는지만 알면 되므로 탐욕적으로 한 번 훑는 것으로 충분합니다.

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

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

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

테스트 #1

테스트 #2

테스트 #3

인자들

s = "ace"
t = "abcde"

예상 출력

true