Regular Expression Matching
문자열 s와 패턴 p가 주어집니다. 패턴에서 문자는 같은 문자와 일치하고, 점 .은 임의의 문자 하나와 일치하며, 별표 *는 바로 앞의 요소(문자 또는 점)가 0개 이상 반복됨을 의미합니다. 패턴이 s 전체와 일치하면 true를 반환하고, 그렇지 않으면 false를 반환하세요.
함수
- sstring
- 일치시킬 문자열, 소문자만
- pstring
- 문자, 점, 별표의 패턴
- 반환값boolean
- p가 s의 모든 항목과 일치하면 true이고, 그렇지 않으면 false입니다.
제약 조건
1 ≤ s.length ≤ 10001 ≤ p.length ≤ 1000s에는 소문자 영어 알파벳만 포함되어 있습니다.p에는 소문자 영어 문자,.및*만 포함됩니다.- 모든
*는 문자 또는.뒤에 오므로,p는*로 시작하지 않으며 별표가 두 개 연속으로 나타나지도 않습니다.
예제
- 입력
- s = "moon"p = "mo*n"
- 출력
- true
- 설명
o*는 o 문자를 모두 포함하므로, m,o*와 n을 합치면 정확히moon이 됩니다.
- 입력
- s = "tree"p = "t.e"
- 출력
- false
- 설명
t.e는tree의 시작 부분인tre와 일치하지만, 마지막 e가 남으며 일치는s전체를 포함해야 합니다.
- 입력
- s = "sky"p = "z*s.*y"
- 출력
- true
- 설명
z*는 z를 0개 취하고, s는 s와 일치하며,.*는 k를 취하고, y는 y와 일치합니다.
후속 질문
같은 표에서 +도 지원할 수 있나요? 이 기호 앞에 있는 요소가 한 개 이상 반복되는 경우를 말합니다.
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
문자 하나와 그 뒤에 오는
*를 하나의 단위로 취급하세요. 그 단위를s의 다음 문자와 비교할 때, 어떤 두 가지 동작을 할 수 있나요?이 단위는 아무것도 일치시키지 않고 건너뛰거나, 문자 하나와 일치한 뒤 그 자리에 머물면서 더 많은 문자를 받을 준비를 할 수 있습니다. 다른 모든 패턴 문자는 정확히 문자 하나와 일치해야 합니다. 별표가 나올 때마다 두 가지 동작을 모두 시도하면 많은 작업이 반복됩니다.
s의 각 접두사가p의 각 접두사와 일치하는지 표에 저장합니다. 빈 문자열에 해당하는 행을 먼저 채우세요. 이 행에서는a*b*와 같은 패턴만 일치합니다. 별표가 있는 칸은 바로 왼쪽에서 두 칸 떨어진 칸이 참이거나, 해당 요소가 문자와 일치하고 바로 위 칸이 참이면 참입니다.
풀이
별표는 임의의 개수만큼 반복될 수 있으며, 적절한 반복 횟수는 뒤에 오는 내용에 따라 달라집니다. 문자와 그 별표를 두 가지 동작이 가능한 하나의 단위로 생각하세요. 건너뛰거나, 문자 하나를 소비하고 그 단위에 머무르는 것입니다. s의 각 접두사와 p의 각 접두사가 일치하는지 나타내는 표를 사용하면 모든 경우를 한 번씩 시도할 수 있습니다.
재귀를 사용해 왼쪽부터 일치시키기
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
접미사를 비교합니다. match(i, j)는 s[i:]가 p[j:]와 일치하는지 나타냅니다. 별표가 없는 문자나 점은 s[i]와 일치해야 하며, 나머지도 일치해야 합니다. 단위 x*는 0개를 사용하고 건너뛰거나, s[i]를 소비하고 같은 단위에 머뭅니다. 이것이 별표 하나로 문자를 원하는 개수만큼 처리하는 방법입니다. 두 분기가 별표가 선택할 수 있는 모든 경우를 다루므로 일치하는 경우를 놓치지 않습니다.
별표 하나마다 탐색은 두 갈래로 나뉩니다. 문자 a 30개와 a*를 열 번 반복한 뒤 b가 있는 경우, 재귀는 답이 거짓이라고 판단하기 전에 별표들에 문자를 나누어 할당하는 약 8.5 × 10^8가지 방법을 시도합니다. 하지만 서로 다른 쌍 (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개 문자와 일치하는지를 나타낸다고 합시다. dp[0][0]은 true입니다. 0번째 행에서 빈 문자열은 접두 패턴의 모든 요소에 별표가 붙어 있는 경우에만 일치합니다. 예를 들면 z* 또는 a*b*와 같습니다.
p[j-1]의 문자나 점은 s[i-1]과 일치해야 하며, 나머지도 대각선 위치인 dp[i-1][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*s.* 열은 0회 복사로 s에서 true가 되고, 이어서 sk와 sky에서 각각 한 칸씩 위로 이동합니다.
각 셀은 바로 위 행이나 왼쪽 셀을 참조하므로, 행별로 채우면 필요한 값이 이미 준비되어 있습니다.
알고리즘
(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], 복사본이 하나 더 있는 경우는 prev[j], 일반적인 일치의 경우는 prev[j-1]입니다. 메모리는 약 10^6개의 셀에서 1001개짜리 행 두 개로 줄어듭니다. 문자열과 패턴은 서로 다른 역할을 하므로 행을 짧게 만들기 위해 입력을 서로 바꿀 수는 없습니다.
알고리즘
prev에 테이블의 0행을 채웁니다.s의 각 문자에 대해cur[0]을 false로 설정하고, 위 행의 값을 위해prev를 읽으며 테이블의 규칙에 따라cur[1..m]을 채웁니다.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*를 비교하면 false가 됩니다. - 첫 번째 셀 이후에도 0번 행을 false로 둡니다. 그러면
b와a*b를 비교할 때 실패합니다. b가 일치하려면a*가 빈 접두사와 일치해야 하기 때문입니다. - 별이 아니라 별의 요소인
p[j-2]를s[i-1]와 비교합니다. 그러면a와a*를 비교할 때 실패합니다. - 두 행 버전에서
cur[0]을 false로 재설정하지 않습니다. 교환 후 기본 행의 true가 남을 수 있으므로aab와b를 비교하면 true가 됩니다.
자주 묻는 질문3
정규식 매칭의 시간 복잡도는 얼마인가요?
표를 사용하는 해결 방법은 길이가 n인 문자열과 길이가 m인 패턴에 대해 O(n × m) 시간이 걸립니다. 각 셀은 다른 셀을 최대 두 개 읽기 때문입니다. 전체 표를 사용하면 O(n × m) 메모리가 필요하고, 두 행만 사용하면 O(m) 메모리가 필요합니다. 단순 재귀는 별표가 많은 패턴에서 지수 시간이 걸릴 수 있습니다.
와일드카드 매칭과는 어떻게 다른가요?
와일드카드 매칭에서는 파일 이름 패턴과 마찬가지로 *는 단독으로 사용되며 임의의 문자 시퀀스와 일치하고, ?는 문자 하나와 일치합니다. 여기서 *는 앞에 있는 요소만 반복하며, 임의의 텍스트는 .*입니다. 둘 다 접두사에 대한 표를 사용하지만, 와일드카드 별표는 dp[i][j-1] 또는 dp[i-1][j]를 참조합니다.
왜 해당 언어의 정규식 라이브러리를 사용하지 않나요?
면접관은 라이브러리 호출이 아니라 알고리즘을 원합니다. 많은 정규식 엔진도 첫 번째 접근법의 느린 재귀 방식인 백트래킹으로 일치 항목을 찾기 때문에, a*를 열 번 복사한 뒤 b를 붙여 긴 a 문자 연속에 적용하면 실행에 몇 분이 걸릴 수 있습니다. 표 방식은 항상 O(n × m)에 끝납니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def isMatch(s, p):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
테스트 #3
인자들
s = "moon" p = "mo*n"
예상 출력
true