[LeetCode] 10. Regular Expression Matching

https://leetcode.com/

Given an input string s and a pattern p, implement regular expression matching with support for ' . ' and ' * ' where:

• ' . '   Matches any single character.​​​​
• ' * '   Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

Example 1:

Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

 

Example 2:

Input: s = "aa", p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

 

Example 3:

Input: s = "ab", p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

 

Constraints:

• 1 <= s.length <= 20
• 1 <= p.length <= 20
• s  contains only lowercase English letters.
• p  contains only lowercase English letters, ' . ' , and ' * ' .
• It is guaranteed for each appearance of the character ' * ' , there will be a previous valid character to match.

 

Code :

var isMatch = function (s, p) {
    const rows = s.length;
    const columns = p.length;
    // 기본 조건들
    if (rows == 0 && columns == 0) {
        return true;
    }
    if (columns == 0) {
        return false;
    }
    // DP 배열
    const dp = Array.from({ length: s.length + 1 }, () => [false]);
    // 빈 문자열과 빈 패턴은 일치
    dp[0][0] = true;
    // *이 포함된 패턴 처리
    for (let i = 1; i < columns + 1; i++) {
        if (p[i - 1] === '*') {
            dp[0][i] = dp[0][i - 2];
        }
        else {
            dp[0][i] = false;
        };
    }
    // 나머지 문자에 대한 처리
    for (let i = 1; i < rows + 1; i++) {
        for (let j = 1; j < columns + 1; j++) {
            if (p[j - 1] === '*') {
                if (p[j - 2] === s[i - 1] || p[j - 2] === '.') {
                    dp[i][j] = dp[i][j - 2] || dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i][j - 2];
                }
            } else if (p[j - 1] === s[i - 1] || p[j - 1] === '.') {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = false;
            }
        }
    }
    return dp[rows][columns];
};

 

Solutions Code :

var isMatch = function(s, p) {
    const m = s.length, n = p.length;
    const dp = new Array(m+1).fill().map(() => new Array(n+1).fill(false));
    dp[0][0] = true; // 빈 패턴은 빈 문자열과 일치
    // 첫 번째 행 (빈 문자열) 초기화
    for (let j = 1; j <= n; j++) {
        if (p[j-1] === '*')
        dp[0][j] = dp[0][j-2];
    }
    // 나머지 셀 채우기
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
        if (s[i-1] === p[j-1] || p[j-1] === '.') {
            dp[i][j] = dp[i-1][j-1];
        } else if (p[j-1] === '*') {
            dp[i][j] = dp[i][j-2]; // 0회 발생
            if (s[i-1] === p[j-2] || p[j-2] === '.') {
            dp[i][j] = dp[i][j] || dp[i-1][j]; // 1회 이상 발생
            }
        }
        }
    }
    return dp[m][n];
}

 

출처 : https://leetcode.com/problemset/all/

Problems - LeetCode