JavaScript로 정규식 매칭 구현하기: '.'과 '*' 패턴 처리

문제 개요

입력 문자열 str과 패턴 p가 주어졌을 때, 마침표(.)와 별표(*)를 지원하는 정규식 매칭 기능을 직접 구현해야 합니다.

각 기호의 역할은 다음과 같습니다.

. → 임의의 단일 문자 하나와 일치합니다.
* → 바로 앞에 오는 문자가 0번 이상 반복되는 경우와 일치합니다.

여기서 중요한 점은 매칭이 입력 문자열 전체를 덮어야 한다는 것입니다. 부분 일치는 인정되지 않습니다.

제약 조건

str은 비어 있을 수 있으며, 소문자 a~z만 포함합니다.
p는 비어 있을 수 있으며, 소문자 a~z와 '.', '*' 문자만 포함합니다.

예시

입력이 다음과 같다고 가정해 보겠습니다.

const str = 'aa';
const p = 'a';

이 경우 결과는 false입니다. 패턴 'a'는 문자열 'aa' 전체와 일치하지 않기 때문입니다.

풀이 접근법: 동적 프로그래밍

이 문제는 동적 프로그래밍(DP)으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 2차원 불리언 테이블 match를 만들어, match[row][col]에 "문자열의 앞에서 row개 문자와 패턴의 앞에서 col개 문자가 서로 일치하는가?"라는 값을 저장하는 것입니다.

테이블을 채우는 규칙은 다음과 같이 정리할 수 있습니다.

패턴 문자가 '*'인 경우: '*'와 그 앞 문자를 함께 제거했을 때 이미 일치했다면(match[row][col-2]) true입니다. 또는 '*' 앞의 문자가 현재 문자열의 문자와 같거나 '.'이면서, 문자열에서 한 글자를 줄여도 여전히 일치한다면(match[row-1][col]) true입니다.
패턴 문자가 일반 문자 또는 '.'인 경우: 현재 문자와 패턴 문자가 같거나 패턴이 '.'일 때, 이전 상태 match[row-1][col-1]의 값을 그대로 계승합니다.
그 외의 경우에는 false입니다.

최종적으로 match[str.length][p.length] 값이 전체 문자열과 전체 패턴의 일치 여부를 나타내며, 빈 패턴 초기화 단계에서 '*'가 연속해서 나오는 경우를 처리하기 위해 첫 행(row 0)을 별도로 채워 주는 것이 핵심 포인트입니다.

구현 코드

const regexMatching = (str, p) => {
    const ZERO_OR_MORE_CHARS = '*';
    const ANY_CHAR = '.';
    const match = Array(str.length + 1).fill(null).map(() => {
        return Array(p.length + 1).fill(null);
    });
    match[0][0] = true;
    for (let col = 1; col <= p.length; col += 1) {
        const patternIndex = col - 1;
        if (p[patternIndex] === ZERO_OR_MORE_CHARS) {
            match[0][col] = match[0][col - 2];
        } else {
            match[0][col] = false;
        }
    }
    for (let row = 1; row <= str.length; row += 1) {
        match[row][0] = false;
    }
    for (let row = 1; row <= str.length; row += 1) {
        for (let col = 1; col <= p.length; col += 1) {
            const stringIndex = row - 1;
            const patternIndex = col - 1;
            if (p[patternIndex] === ZERO_OR_MORE_CHARS) {
                if (match[row][col - 2] === true) {
                    match[row][col] = true;
                } else if (
                    (
                        p[patternIndex - 1] === str[stringIndex]
                        || p[patternIndex - 1] === ANY_CHAR
                    )
                    && match[row - 1][col] === true
                ) {
                    match[row][col] = true;
                } else {
                    match[row][col] = false;
                }
            } else if (
                p[patternIndex] === str[stringIndex]
                || p[patternIndex] === ANY_CHAR
            ) {
                match[row][col] = match[row - 1][col - 1];
            } else {
                match[row][col] = false;
            }
        }
    }
    return match[str.length][p.length];
};
console.log(regexMatching('aab', 'c*a*b'));

실행 결과

콘솔에 출력되는 결과는 다음과 같습니다.

true

'aab'와 'c*a*b'의 경우를 살펴보면, 'c*'는 0개의 c와 일치하고, 'a*'는 연속된 두 개의 a와 일치하며, 마지막 'b'가 남은 b와 일치합니다. 따라서 전체 문자열이 패턴과 일치하므로 true가 반환됩니다.