문제 개요
문자열 s와 정규 표현식 패턴 p가 주어졌을 때, 주어진 패턴이 문자열 전체와 일치하는지 확인하는 프로그램을 작성해야 합니다. 이 문제에서 정규 표현식은 다음 두 가지 규칙만 지원합니다.
- . (마침표) — 임의의 단일 문자 하나와 일치합니다.
- * (별표) — 바로 앞의 요소가 0번 이상 반복되는 경우와 일치합니다.
예를 들어 입력이 pattern = "h.l*o", s = "hello"라면 결과는 True입니다. 'h'는 'h'와, '.'은 'e'와, 'l*'은 연속된 'll'과, 마지막 'o'는 'o'와 각각 일치하기 때문입니다.
해결 접근 방법
이 문제는 재귀(백트래킹) 방식으로 해결할 수 있습니다. 문자열과 패턴을 앞에서부터 한 글자씩 비교하면서, '*'를 만나면 앞 문자를 건너뛰는 경우와 반복해서 소비하는 경우를 모두 시도합니다. 구체적인 알고리즘은 다음과 같습니다.
- n := 문자열 s의 길이, m := 패턴 p의 길이로 설정합니다.
- 인덱스 i(문자열의 현재 위치)와 j(패턴의 현재 위치)를 받는 dp(i, j) 함수를 정의합니다.
- j가 m과 같으면(패턴을 모두 소진), i가 n과 같은지(문자열도 모두 소진되었는지) 여부를 반환합니다.
- match는 i < n이고 (s[i]가 p[j]와 같거나 p[j]가 '.')일 때 true, 그렇지 않으면 false입니다.
- j + 1 < m이고 p[j + 1]이 '*'라면, dp(i, j + 2)(별표와 앞 문자를 건너뜀) 또는 (match이고 dp(i + 1, j))(현재 문자를 별표로 소비) 중 하나라도 true이면 true를 반환합니다.
- 그 외의 경우에는 match이고 dp(i + 1, j + 1)인지 여부를 반환합니다.
- 메인 메서드에서는 dp(0, 0)의 결과를 반환합니다.
예제 코드
더 나은 이해를 돕기 위해 다음 파이썬 구현을 살펴보겠습니다.
class Solution:
def solve(self, p, s):
n = len(s)
m = len(p)
def dp(i, j):
if j == m:
return i == n
match = i < n and (s[i] == p[j] or p[j] == ".")
if j + 1 < m and p[j + 1] == "*":
return dp(i, j + 2) or (match and dp(i + 1, j))
return match and dp(i + 1, j + 1)
return dp(0, 0)
ob = Solution()
pattern = "h.l*o"
s = "hello"
print(ob.solve(pattern, s))입력
"h.l*o", "hello"출력
True복잡도 및 개선 팁
이 재귀 풀이는 최악의 경우 지수 시간이 걸릴 수 있습니다. 입력 크기가 커지면 functools.lru_cache 같은 메모이제이션을 적용해 dp(i, j)의 중복 호출을 제거하면 시간 복잡도를 O(n × m)으로 최적화할 수 있습니다.