[Leetcode] 10. Regular Expression Matching

🖥️ 시작하며

1️⃣ 문제 접근법

2️⃣ 점화식, 기저 조건 설정

1. DP 테이블 정의
dp[i][j]는 문자열 s의 처음 i 문자(s[0..i-1])와 패턴 p의 처음 j 문자(p[0..j-1])가 일치하는지를 나타낸다.

2. 기본 사례 설정
1. 빈 문자열과 빈 패턴:
dp[0][0] = True (빈 문자열은 빈 패턴과 일치하게 된다. 기저 조건을 설정한다.)
2. 빈 문자열과 패턴:
패턴이 * 를 포함하여 빈 문자열과 일치할 수 있는 경우를 고려한다. 패턴이 "a*" 또는 "a*b*"인 경우다. 이를 위해 dp[0][j]를 초기화하자.

3️⃣ 점화식 유도

1. 직접 일치 또는 점 연산자
• 조건: p[j-1] == s[i-1] 또는 p[j-1] == '.'
• 이는 현재 패턴 문자가 문자열의 현재 문자와 일치하거나, .을 사용하여 일치하는 경우다.
→ dp[i][j] = dp[i-1][j-1] (직관적으로 이전 상태를 가져오는 것을 알 수 있다)

2. 별표 연산자
• 조건: p[j-1] == '*'
• 이는 * 가 바로 앞의 문자가 0회 이상 반복되는 것을 의미한다.
• * 는 두 가지 상황을 고려할 수 있다.
a. 0회 발생 (문자 제거):
• * 와 그 앞의 문자를 패턴에서 제거하여 현재 문자열과 패턴의 이전 상태를 비교
→ dp[i][j] = dp[i][j-2]
b. 1회 이상 발생 (문자 반복):
• * 앞의 문자가 현재 문자열의 문자와 일치하거나, .인 경우
• 이때, 패턴의 * 를 이용하여 문자열의 이전 문자까지 매칭된 상태를 확인
→ dp[i][j] = dp[i][j] or dp[i-1][j]
종합하면:

if p[j-1] == '*':
    dp[i][j] = dp[i][j-2]
    if p[j-2] == s[i-1] or p[j-2] == '.':
        dp[i][j] = dp[i][j] or dp[i-1][j]

점화식 요약

# DP 테이블 채우기
for i in range(1, len(s) + 1):
    for j in range(1, len(p) + 1):
        # 현재 문자가 매치되는 경우 (같은 문자이거나 '.'인 경우)
        if p[j - 1] == s[i - 1] or p[j - 1] == ".":
            # 현재 문자가 매치되면, 이전 상태의 매치 여부를 그대로 가져옴
            # 즉, 현재 문자를 제외한 이전까지의 매치 상태를 유지
            dp[i][j] = dp[i - 1][j - 1]

        # 현재 패턴 문자가 '*'인 경우
        elif p[j - 1] == "*":
            # 1. '*' 앞의 문자를 무시하는 경우 (0번 사용)
            # '*'와 그 앞의 문자를 모두 무시하고, 그 이전 상태의 매치 여부를 가져옴
            dp[i][j] = dp[i][j - 2]

            # 2. '*' 앞의 문자가 현재 문자와 매치되거나 '.'인 경우
            if p[j - 2] == s[i - 1] or p[j - 2] == ".":
                # '*' 앞의 문자를 한 번 이상 사용하는 경우
                # 현재 문자를 매치시키고, 이전 문자열 상태의 매치 여부를 확인
                # 'or' 연산은 이전 단계(dp[i][j - 2])와 현재 단계 중 하나라도 참이면 참
                dp[i][j] = dp[i][j] or dp[i - 1][j]

💡 점화식의 직관적 이해

4️⃣ 예제를 통한 점화식 적용 이해

예제:

• 입력: s = "aab", p = "c*a*b"

• 목표: dp[3][5]의 값을 구하는 것

단계별 과정:

1. 초기화:
• dp[0][0] = True
• dp[0][2] = True ("c*"는 0회 발생)
• dp[0][4] = True ("c*a*"는 0회 발생)

2. DP 테이블 채우기:

ㅤ	빈 문자	c	*	a	*	b
빈 문자	T	F	T	F	T	F
a	F	F	F	T	T	F
a	F	F	F	F	T	F
b	F	F	F	F	F	T

• 각 dp[i][j]는 이전 상태들을 참조하여 채워진다.
• 예를 들어 dp[1][3] ("a" vs "c*a")는 dp[0][2] ("" vs "c*")을 참조하여 True가 된다.

⚙️ Python

from typing import List
from itertools import zip_longest


class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        # DP 테이블 초기화
        dp = [[False] * (len(p) + 1) for _ in range(len(s) + 1)]

        # 빈 문자열과 빈 패턴은 매치됨
        dp[0][0] = True

        # 패턴이 '*'로 시작하는 경우 처리
        # 이 경우 빈 패턴과 매치될 수 있음
        for j in range(1, len(p) + 1):
            if p[j - 1] == "*":
                dp[0][j] = dp[0][j - 2]

        # DP 테이블 채우기
        for i in range(1, len(s) + 1):
            for j in range(1, len(p) + 1):
                # 현재 문자가 매치되는 경우 (같은 문자이거나 '.'인 경우)
                if p[j - 1] == s[i - 1] or p[j - 1] == ".":
                    # 현재 문자가 매치되면, 이전 상태의 매치 여부를 그대로 가져옴
                    # 즉, 현재 문자를 제외한 이전까지의 매치 상태를 유지
                    dp[i][j] = dp[i - 1][j - 1]

                # 현재 패턴 문자가 '*'인 경우
                elif p[j - 1] == "*":
                    # 1. '*' 앞의 문자를 무시하는 경우 (0번 사용)
                    # '*'와 그 앞의 문자를 모두 무시하고, 그 이전 상태의 매치 여부를 가져옴
                    dp[i][j] = dp[i][j - 2]

                    # 2. '*' 앞의 문자가 현재 문자와 매치되거나 '.'인 경우
                    if p[j - 2] == s[i - 1] or p[j - 2] == ".":
                        # '*' 앞의 문자를 한 번 이상 사용하는 경우
                        # 현재 문자를 매치시키고, 이전 문자열 상태의 매치 여부를 확인
                        # 'or' 연산은 이전 단계(dp[i][j - 2])와 현재 단계 중 하나라도 참이면 참
                        dp[i][j] = dp[i][j] or dp[i - 1][j]

        # 최종 결과 반환
        return dp[len(s)][len(p)]


if __name__ == "__main__":
    sol = Solution()
    print(sol.isMatch("aab", "c*a*b"))

📌 소감