고전적인 Regular Expression Matching 문제에서는 일반 문자와 다음 두 연산자를 가진 Pattern을 사용합니다.
. → 임의의 한 문자
* → 이전 요소를 0번 이상 반복예:
s = "aa"
p = "a*"결과는 true입니다.
Dot
.은 정확히 한 문자를 의미합니다.
c.t는 cat, cut, c9t와 Match할 수 있습니다.
Star
*는 앞 요소에 적용됩니다.
a*는 빈 문자열부터 여러 개의 a까지 표현할 수 있습니다.
Dynamic Programming
다음을 정의합니다.
dp[i][j]첫 번째 i개의 String 문자와 첫 번째 j개의 Pattern 문자가 완전히 Match하는지를 의미합니다.
dp[0][0] = true또한 a*b*c* 같은 Pattern은 모든 Star를 0번 사용할 수 있으므로 빈 String과도 Match합니다.
일반 문자 또는 Dot
현재 문자가 같거나 Pattern이 .이면:
dp[i][j] = dp[i - 1][j - 1]Star
먼저 이전 요소와 *를 사용하지 않는 경우:
dp[i][j] = dp[i][j - 2]이전 Pattern 요소가 현재 String 문자와 Match한다면 하나를 더 Consume할 수 있습니다.
dp[i][j] = dp[i][j] || dp[i - 1][j]TypeScript
function isRegexMatch(s: string, p: string): boolean {
const dp = Array.from(
{ length: s.length + 1 },
() => new Array(p.length + 1).fill(false)
);
dp[0][0] = true;
for (let j = 2; j <= p.length; j++) {
if (p[j - 1] === '*') {
dp[0][j] = dp[0][j - 2];
}
}
for (let i = 1; i <= s.length; i++) {
for (let j = 1; j <= p.length; j++) {
if (
p[j - 1] === '.' ||
p[j - 1] === s[i - 1]
) {
dp[i][j] = dp[i - 1][j - 1];
} else if (p[j - 1] === '*') {
dp[i][j] = dp[i][j - 2];
if (
p[j - 2] === '.' ||
p[j - 2] === s[i - 1]
) {
dp[i][j] =
dp[i][j] || dp[i - 1][j];
}
}
}
}
return dp[s.length][p.length];
}복잡도
Time Complexity: O(n × m)
Space Complexity: O(n × m)Memoization
Recursive하게도 해결할 수 있습니다.
x*를 만나면:
x*를 0번 사용또는 현재 문자가 맞으면:
문자 하나를 Consume하고 x* 유지두 Branch가 생깁니다.
Memoization이 없으면 같은 상태를 반복 계산할 수 있습니다.
Regex와 Wildcard 차이
Regex에서는:
* → 이전 요소 반복Wildcard Matching에서는 보통:
* → 임의의 문자열이므로 의미가 다릅니다.
Full Match
이 문제에서는 Pattern이 전체 String을 Match해야 합니다.
따라서 ell은 hello 전체와 Match하지 않습니다.
실제 활용
실제 Regex는 Validation, Search, Log Filtering, Text Processing 등에 사용됩니다.
애플리케이션에서는 직접 Regex Engine을 구현하기보다 언어에서 제공하는 검증된 Engine을 사용하는 것이 일반적입니다.
면접 핵심
.의미*의미- DP State
- Empty String 처리
- 0회/여러 회 반복
O(n × m)복잡도
정리
Regular Expression Matching은 재귀적 Branching 문제를 Dynamic Programming으로 바꾸는 대표적인 예제입니다.