문제 개요
입력 문자열 s와 패턴 문자열 p가 주어졌다고 가정해 봅시다. 여기서 s는 원본 문자열이고, p는 매칭에 사용할 패턴입니다. 우리는 문자열 안에서 패턴과 일치하는 부분을 찾아내는 메서드를 하나 정의해야 합니다. 즉, 다음 두 특수 문자를 지원하는 정규 표현식 매칭 기능을 직접 구현하는 것이 목표입니다.
점(.) — 임의의 단일 문자 하나와 일치합니다.
별표(*) — 바로 앞에 있는 문자가 0번 이상 반복되는 경우와 일치합니다.
예를 들어, 입력이 s = "aa", p = "a."라면 '.'이 임의의 한 글자와 대응되므로 결과는 True입니다. 같은 입력 문자열에 대해 패턴이 ".*"라면 '임의의 문자가 0번 이상 반복'된다는 의미이므로 역시 True가 됩니다.
해결 전략: 동적 계획법(DP)
이 문제는 동적 계획법(Dynamic Programming)을 이용하면 효율적으로 해결할 수 있습니다. 각 단계는 다음과 같습니다.
ss := 문자열 s의 길이, ps := 패턴 p의 길이로 설정합니다.
(ss+1) × (ps+1) 크기의 DP 테이블(dp)을 만들고 모든 값을 False로 초기화합니다.
인덱스 계산을 편하게 하기 위해 p와 s 앞에 공백 한 칸을 추가합니다.
i를 2부터 ps까지 순회하며 다음을 수행합니다.
p[i]가 '*'라면 dp[0][i] := dp[0][i-2]로 설정하고, 그렇지 않으면 False로 둡니다. (빈 문자열과 패턴의 선행 일치 여부 처리)
i를 1부터 ss까지, j를 1부터 ps까지 이중 반복하며 다음 규칙을 적용합니다.
s[i] == p[j]이거나 p[j]가 '.'이라면 → dp[i][j] := dp[i-1][j-1]
그렇지 않고 p[j]가 '*'라면 →
dp[i][j] := dp[i][j-2] ('*' 앞 문자를 0번 사용하는 경우)
s[i] == p[j-1]이거나 p[j-1]이 '.'이라면 → dp[i][j] := max(dp[i][j], dp[i-1][j]) ('*' 앞 문자를 한 번 더 소비하는 경우)
최종적으로 dp[ss][ps]를 반환합니다. 이 값이 곧 전체 문자열과 패턴의 일치 여부입니다.
구현 예제
아래 파이썬 코드를 통해 실제 구현 방법을 확인해 보겠습니다.
class Solution(object):
def isMatch(self, s, p):
ss = len(s)
ps = len(p)
dp = [[False for i in range(ps+1)] for j in range(ss+1)]
p = " " + p
s = " " + s
dp[0][0] = True
for i in range(2, ps+1):
dp[0][i] = dp[0][i-2] if p[i]=='*' else False
for i in range(1, ss+1):
for j in range(1, ps+1):
if s[i] == p[j] or p[j]=='.':
dp[i][j] = dp[i-1][j-1]
elif p[j] == '*':
dp[i][j] = dp[i][j-2]
if s[i] == p[j-1] or p[j-1]=='.':
dp[i][j] = max(dp[i][j], dp[i-1][j])
return dp[ss][ps]
ob = Solution()
print(ob.isMatch("aa", "a."))
print(ob.isMatch("aaaaaa", "a*"))입력
"aa", "a." "aaaaaa", "a*"
출력
True True
정리
이 알고리즘은 시간 복잡도 O(ss × ps), 공간 복잡도 O(ss × ps)로 동작합니다. '*' 처리 시 '앞 문자를 건너뛰는 경우'와 '한 번 더 소비하는 경우'를 함께 고려하는 것이 핵심 포인트이며, 이러한 DP 접근 방식은 LeetCode의 'Regular Expression Matching' 문제 등 다양한 코딩 테스트에서 자주 활용됩니다.