Regular Expression Matching

Q: 정규 표현식 매칭의 시간 복잡도는 무엇인가요?

표를 사용하는 해결 방법은 O(n × m) 시간이 걸립니다. 각 셀이 다른 셀을 최대 두 개 읽기 때문이며, 여기서 n 은 s 의 길이이고 m 은 p 의 길이입니다. 전체 표에는 O(n × m) 메모리가 필요하고, 두 행을 사용하면 O(m) 이 필요합니다. 별표가 많은 패턴에서는 단순 재귀가 지수 시간이 걸릴 수 있습니다.

Q: 별 셀은 왜 대각선 셀이 아니라 바로 위의 셀을 읽을까요?

위쪽 셀인 dp[i-1][j] 은 s 의 문자가 하나 적고 별표는 여전히 포함된 동일한 패턴입니다. 따라서 별표가 s[i-1] 을 먹은 다음에는 s[i-2] 도 먹을 수 있고, 열을 따라 계속 위로 올라가며 같은 방식으로 처리할 수 있습니다. 대각선 방향의 셀인 dp[i-1][j-2] 는 문자 하나를 처리한 뒤 별표를 제거하므로, 임의의 개수가 아니라 정확히 한 개만 허용합니다.

Q: 와일드카드 매칭과는 어떻게 다른가요?

파일 이름 패턴에서처럼 와일드카드 매칭에서 * 는 단독으로 사용되어 문자들의 모든 연속열과 일치하고, ? 는 문자 하나와 일치합니다. 여기서 * 는 바로 앞의 요소만 반복하며, 임의의 텍스트 패턴은 .* 입니다. 둘 다 접두사에 대한 표를 사용해 해결하지만, 별표 전이는 다릅니다. 와일드카드에서는 dp[i][j-1] 또는 dp[i-1][j] 를 읽습니다.

어려움동적 계획법 재귀

+10

문자열 s와 패턴 p가 주어집니다. 패턴에서 문자는 같은 문자와 일치하고, 점 .은 임의의 문자 하나와 일치하며, 별표 *는 바로 앞에 있는 요소(문자 또는 점)가 0개 이상 반복됨을 의미합니다. 패턴이 일부가 아닌 s 전체와 일치하면 true를 반환하고, 그렇지 않으면 false를 반환합니다.

함수

isMatch(s: string, p: string) → boolean

sstring: 일치시킬 문자열, 소문자만 사용
pstring: 문자, 점, 별표의 패턴
반환값boolean: true는 p가 s의 모든 부분과 일치하면, 그렇지 않으면 false

제약 조건

1 ≤ s.length ≤ 1000
1 ≤ p.length ≤ 1000
s에는 소문자 영어 문자만 포함되어 있습니다.
p에는 소문자 영문자, . 및 *만 포함됩니다.
모든 *는 문자 또는 . 뒤에 오므로, p는 *로 시작하지 않으며 별표 두 개가 연속으로 나오지도 않습니다.

예제

입력: s = "moon"p = "mo*n"
출력: true
설명: o*는 o 문자를 모두 포함하므로, m, o*와 n을 합치면 정확히 moon이 됩니다.

입력: s = "tree"p = "t.e"
출력: false
설명: t.e는 세 글자로 된 문자열만 일치합니다. 즉, t, 임의의 문자 하나, 그리고 e입니다. tree의 시작 부분에 있는 tre와 일치하지만, 마지막 e는 남으며, 일치하는 부분은 s 전체를 포함해야 합니다.

입력: s = "sky"p = "z*s.*y"
출력: true
설명: z*는 z를 0개 가져오고, s는 s와 일치하며, .*는 k를 가져오고, y는 y와 일치합니다. 별표가 붙은 문자는 아무것도 나타내지 않을 수 있으므로, sky에 나타나지 않는 z는 비용이 들지 않습니다.

제출 시 숨은 테스트 +29개

후속 질문

같은 표에서 +와 그 앞 요소의 복사본을 하나 이상 지원할 수도 있나요?

힌트

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

3개 중 0개 열림

풀이

별표는 복사본을 몇 개든 취할 수 있으며, 적절한 개수는 뒤에 무엇이 오는지에 따라 달라집니다. 가능한 한 많이 취하면 실패합니다. aaa에 대해 패턴 a*a는 a*가 세 글자를 모두 먹어 버려 마지막 a에 남는 것이 없게 합니다. 이 문제를 해결하는 핵심은 문자와 그 별표를 두 가지 동작을 하는 하나의 단위로 취급하는 것입니다. 건너뛰거나, 문자 하나를 먹고 현재 위치에 머무를 수 있습니다. 표에는 s의 각 접두사가 p의 각 접두사와 일치하는지가 기록되므로 모든 선택을 한 번씩 시도할 수 있고, 이 표의 두 행이면 충분합니다.

재귀를 사용하여 왼쪽부터 일치시키기

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

핵심 아이디어

match(i, j)가 접미사 s[i:]가 접미사 p[j:]와 일치하는지 답한다고 하자. 패턴을 모두 사용했다면 문자열도 모두 사용한 경우에만 일치한다. 그렇지 않으면 first를 계산한다. 즉, s[i]에 문자가 있고 p[j]가 그 문자이거나 점이다.

이제 한 문자 앞을 살펴보자. p[j+1]이 별표라면 p[j]*는 두 가지 이동을 할 수 있는 하나의 단위다. 문자를 0개 선택할 수 있다. match(i, j+2)로 두 문자를 모두 건너뛴다. 또는 first가 참이면 문자를 1개 선택할 수 있다. s[i]를 소비하고 같은 단위에 머물면서 match(i+1, j)를 호출해 다음 문자를 선택할 준비를 한다. j에 머무르기 때문에 별표 하나로 문자를 하나씩 원하는 개수만큼 선택할 수 있다. 별표가 없으면 p[j]는 문자 하나와 정확히 일치해야 한다. 즉, first and match(i+1, j+1)이다.

별표 하나마다 탐색이 둘로 나뉘고 실패는 흔히 맨 마지막에야 발견되기 때문에 느리다. a*를 열 번 반복한 다음 b가 오는 패턴에 a 문자 30개를 입력한다고 하자. 재귀는 a 문자 30개 중 일부 또는 전부를 열 개의 별표에 나누는 모든 방법을 시도한다. 그 방법은 약 8.5 × 10^8가지이며, false라고 답하기 전에 약 2 × 10^9번 호출한다. 큰 테스트에는 문자가 1000개 있다. 하지만 서로 다른 (i, j) 쌍은 (n+1) × (m+1)개뿐이다.

알고리즘

i와 j에서 시작하는 접미사에 대해 match(i, j)를 작성하세요.
j가 p의 끝을 지났다면, i가 s의 끝을 지났는지 여부를 반환하세요.
s[i]가 존재하고 p[j]가 s[i] 또는 점인지 여부를 first에 설정하세요.
p[j+1]가 별표라면 match(i, j+2) 또는 first and match(i+1, j)를 반환하세요.
그렇지 않으면 first and match(i+1, j+1)을 반환하세요. 답은 match(0, 0)입니다.

def isMatch(s, p):
    n, m = len(s), len(p)

    def match(i, j):
        # Does s[i:] match p[j:]?
        if j == m:
            return i == n
        first = i < n and p[j] in (s[i], ".")
        if j + 1 < m and p[j + 1] == "*":
            # use p[j] zero times, or let it eat s[i] and stay on the same x*
            return match(i, j + 2) or (first and match(i + 1, j))
        return first and match(i + 1, j + 1)

    return match(0, 0)

접두사 표 채우기

핵심 아이디어

상태. dp[i][j]는 s의 처음 i개 문자와 p의 처음 j개 문자가 일치하는지를 나타냅니다. 인덱스 0은 빈 접두사를 뜻합니다.

기본 행과 열. dp[0][0]은 true입니다. 빈 패턴은 빈 문자열과 일치합니다. 그 아래의 0열은 false입니다. 빈 패턴은 문자와 일치할 수 없기 때문입니다. 0행은 조금 까다롭습니다. 패턴의 접두사는 그 안의 모든 요소가 z*나 a*b*처럼 별표가 붙은 경우에만 빈 문자열과 일치합니다. 따라서 p[j-1]가 별표이고 dp[0][j-2]가 true일 때 dp[0][j]는 true입니다.

전이. p[j-1]가 문자 또는 점이면 마지막 문자 s[i-1]와 일치해야 하고, 나머지도 일치해야 합니다. 즉 대각선의 dp[i-1][j-1]입니다. p[j-1]가 별표라면 그 요소는 x = p[j-2]이고, 별표에는 두 가지 선택이 있습니다. 0개 복사: 패턴에서 x*를 제거합니다. 왼쪽으로 두 칸 이동한 dp[i][j-2]입니다. 복사본 하나 더: x가 s[i-1]와 일치하면 해당 문자는 복사본 중 하나이고, 같은 x*가 여전히 더 짧은 문자열을 처리해야 하므로 같은 열에서 바로 위 칸인 dp[i-1][j]를 확인합니다. 복사본 하나마다 해당 열을 한 칸 위로 올라가므로 별표 하나로 임의 개수의 문자를 처리할 수 있습니다.

다음은 sky와 z*s.*y에 대한 표입니다. 열은 접두사 "", z, z*, z*s, z*s., z*s.*, z*s.*y를 나타냅니다(T는 true, F는 false). 행 ""는 [T, F, T, F, F, F, F]입니다. z*만 빈 문자열이 될 수 있습니다. 행 s는 [F, F, F, T, F, T, F]입니다. 위쪽 대각선에서 z*가 빈 문자열이 되어 s가 s와 일치하고, 이어서 .*가 0개 복사본을 취합니다. 행 sk는 [F, F, F, F, T, T, F]입니다. z*s.*에 해당하는 칸은 복사본 하나 더를 통해 true가 됩니다. 점이 k를 처리하며, 바로 위의 T에서 값을 가져옵니다. 행 sky는 [F, F, F, F, F, T, T]입니다. 점 별표가 같은 방식으로 y를 처리하며 열을 한 칸 더 올라가고, 이어서 대각선에서 y가 y와 일치합니다. 마지막 칸은 true입니다.

각 칸은 위쪽 행이나 왼쪽 칸의 값을 확인하므로, 행별로 왼쪽에서 오른쪽으로 채우면 필요한 값이 이미 준비되어 있습니다. 셀 수는 (n+1) × (m+1)개로, 가장 큰 테스트에서 약 10^6개이며 각 셀의 작업은 상수 시간입니다.

알고리즘

(n+1) × (m+1)개의 false 값으로 구성된 dp 테이블을 만들고 dp[0][0]을 true로 설정합니다.
j가 2부터 m까지일 때, p[j-1]이 별표이고 dp[0][j-2]가 true이면 dp[0][j]를 true로 설정합니다.
i ≥ 1 및 j ≥ 1인 각 셀에 대해 p[j-1]이 별표이면 해당 셀을 dp[i][j-2] 또는 (p[j-2]가 s[i-1]와 일치하고 dp[i-1][j])로 설정합니다.
그렇지 않으면 해당 셀을 (p[j-1]이 s[i-1]와 일치함) 및 dp[i-1][j-1]로 설정합니다.
dp[n][m]을 반환합니다.

def isMatch(s, p):
    n, m = len(s), len(p)
    # dp[i][j]: do the first i letters of s match the first j characters of p?
    dp = [[False] * (m + 1) for _ in range(n + 1)]
    dp[0][0] = True  # an empty pattern matches an empty string
    for j in range(2, m + 1):
        # an empty string matches only patterns like x*y*z*
        dp[0][j] = p[j - 1] == "*" and dp[0][j - 2]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if p[j - 1] == "*":
                zero = dp[i][j - 2]  # use p[j-2] zero times
                more = p[j - 2] in (s[i - 1], ".") and dp[i - 1][j]  # one more copy eats s[i-1]
                dp[i][j] = zero or more
            else:
                dp[i][j] = p[j - 1] in (s[i - 1], ".") and dp[i - 1][j - 1]
    return dp[n][m]

두 개의 행만 유지

핵심 아이디어

행 i는 행 i-1에서 대각선 셀과 바로 위 셀, 그리고 현재 행에서 두 칸 왼쪽 셀을 읽습니다. 더 위쪽 행은 다시 읽지 않습니다. 두 배열을 유지하세요. 완성된 행에는 prev를, 채우고 있는 행에는 cur를 사용하고, s의 각 문자 처리가 끝날 때마다 두 배열을 바꾸세요. 전이 규칙은 그대로입니다. 복사 0회는 cur[j-2], 복사 1회 추가는 prev[j], 단순 일치는 prev[j-1]입니다.

빈 문자열의 기본 행을 prev로 설정하고 시작하세요. 각 행을 시작할 때 cur[0]을 false로 설정하세요. 배열을 바꾸면 cur에는 이전 행이 들어 있고, 기본 행의 첫 번째 항목은 true이기 때문입니다.

각 행에는 m + 1개의 항목이 있으므로 메모리 사용량은 약 10^6개의 셀에서 1001개 항목으로 이루어진 두 행으로 줄어듭니다. 편집 거리와 달리 행의 길이를 줄이기 위해 두 입력을 서로 바꿀 수는 없습니다. 문자열과 패턴은 서로 다른 역할을 하기 때문입니다.

알고리즘

기본 행으로 prev를 채웁니다. 0에서는 true로, p[j-1]가 별표이고 prev[j-2]가 true일 때는 j에서 true로 설정합니다.
s의 각 문자에 대해 cur[0]을 false로 설정합니다.
cur[1..m]을 채웁니다. 별표 셀은 cur[j-2] 또는 (요소가 일치하고 prev[j]가 true)입니다. 다른 셀은 (요소가 일치하고) prev[j-1]입니다.
prev와 cur를 서로 바꿉니다.
prev[m]을 반환합니다.

def isMatch(s, p):
    n, m = len(s), len(p)
    # prev[j]: do the letters of s before the current one match the first j characters of p?
    prev = [False] * (m + 1)
    prev[0] = True  # row 0: the empty string
    for j in range(2, m + 1):
        prev[j] = p[j - 1] == "*" and prev[j - 2]  # only patterns like x*y*z* match it
    for i in range(1, n + 1):
        cur = [False] * (m + 1)  # cur[0] stays False: an empty pattern matches no letters
        for j in range(1, m + 1):
            if p[j - 1] == "*":
                zero = cur[j - 2]  # use p[j-2] zero times
                more = p[j - 2] in (s[i - 1], ".") and prev[j]  # one more copy eats s[i-1]
                cur[j] = zero or more
            else:
                cur[j] = p[j - 1] in (s[i - 1], ".") and prev[j - 1]
        prev = cur
    return prev[m]

함정과 경계 사례

잘못된 답은 대부분 별표에서 비롯됩니다. 별표가 무엇을 반복하는지, 몇 번 반복하는지, 그리고 아무것도 일치시키지 않을 수도 있는 위치가 어디인지가 원인입니다.

별표가 가능한 한 많은 문자를 가져가도록 두는 경우입니다. a*a는 aaa와 일치하지만, 탐욕적인 a*가 문자 세 개를 모두 가져가면 마지막 a가 실패합니다.
한 번 더 반복할 때 dp[i-1][j-2]를 읽는 경우입니다. 그러면 별표가 문자를 최대 하나만 가져갈 수 있으므로, aa와 a*를 비교하면 거짓이 됩니다. 별표가 있는 열에 그대로 머무르세요: dp[i-1][j].
첫 번째 셀을 제외하고 0번 행을 모두 거짓으로 두는 경우입니다. 그러면 b가 앞에 있는 빈 접두사와 일치하도록 a*가 필요하기 때문에, b와 a*b의 비교가 실패합니다.
s[i-1]를 별표 자체와 비교하고, 별표의 요소인 p[j-2]와 비교하지 않는 경우입니다.
파일 이름 패턴에서처럼 *를 "임의의 텍스트"로 취급하는 경우입니다. 여기서는 앞에 있는 요소만 반복합니다. 임의의 텍스트는 .*입니다.
부분 일치를 받아들이는 경우입니다. t.e는 tree의 시작 부분과 일치하지만, 문자가 하나 남으므로 답은 거짓입니다.
두 행을 사용하는 버전에서 cur[0] = false를 빠뜨리는 경우입니다. 처음 교환한 뒤에는 cur[0]에 기본 행의 참 값이 들어 있습니다.

자주 묻는 질문4

정규 표현식 매칭의 시간 복잡도는 무엇인가요?

표를 사용하는 해결 방법은 O(n × m) 시간이 걸립니다. 각 셀이 다른 셀을 최대 두 개 읽기 때문이며, 여기서 n은 s의 길이이고 m은 p의 길이입니다. 전체 표에는 O(n × m) 메모리가 필요하고, 두 행을 사용하면 O(m)이 필요합니다. 별표가 많은 패턴에서는 단순 재귀가 지수 시간이 걸릴 수 있습니다.

별 셀은 왜 대각선 셀이 아니라 바로 위의 셀을 읽을까요?

위쪽 셀인 dp[i-1][j]은 s의 문자가 하나 적고 별표는 여전히 포함된 동일한 패턴입니다. 따라서 별표가 s[i-1]을 먹은 다음에는 s[i-2]도 먹을 수 있고, 열을 따라 계속 위로 올라가며 같은 방식으로 처리할 수 있습니다. 대각선 방향의 셀인 dp[i-1][j-2]는 문자 하나를 처리한 뒤 별표를 제거하므로, 임의의 개수가 아니라 정확히 한 개만 허용합니다.

와일드카드 매칭과는 어떻게 다른가요?

파일 이름 패턴에서처럼 와일드카드 매칭에서 *는 단독으로 사용되어 문자들의 모든 연속열과 일치하고, ?는 문자 하나와 일치합니다. 여기서 *는 바로 앞의 요소만 반복하며, 임의의 텍스트 패턴은 .*입니다. 둘 다 접두사에 대한 표를 사용해 해결하지만, 별표 전이는 다릅니다. 와일드카드에서는 dp[i][j-1] 또는 dp[i-1][j]를 읽습니다.

왜 해당 언어의 정규식 라이브러리를 사용하지 않나요?

면접관은 라이브러리 호출이 아니라 알고리즘을 원합니다. 실제 위험도 있습니다. 많은 정규식 엔진은 백트래킹으로 매칭하는데, 이는 첫 번째 접근 방식의 느린 재귀와 같습니다. a*를 열 번 반복한 뒤 b가 오는 패턴을 a 문자가 길게 이어지는 문자열에 적용하면, 이런 엔진은 몇 분 동안 실행될 수 있습니다. 표 방식은 항상 O(n × m) 시간에 끝납니다.

Python

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

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

s = "moon"
p = "mo*n"

기대값

true

Regular Expression Matching

함수

제약 조건

예제

힌트

풀이

재귀를 사용하여 왼쪽부터 일치시키기

접두사 표 채우기

두 개의 행만 유지

함정과 경계 사례

자주 묻는 질문4

비슷한 문제