[LeetCode, 리트코드] Regular Expression Matching

1. Problem

s 문자열과 p 패턴이 주어질 때 '.' 와 '*'가 지원되는 정규표현식을 구현하라.

'.' 어느 하나의 문자와도 매칭된다.
'*' *의 바로 앞에 있는 문자와 0번 이상 매칭된다.

전체 입력 문자열을 다 커버해야한다.

Note:

• s 는 비어있을 수 있으며 소문자 a-z로 구성된다.
• p 는 비어있을 수 있으며 소문자 a-z 그리고 . ,* 와 같은 문자열로 구성된다. 

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 precedeng 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 (.)".

Example 4:

Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".

Example 5:

Input:
s = "mississippi"
p = "mis*is*p*."
Output: false

2. Solution

'.' 와 단일 문자 매칭되었을 때는 큰 어려움이 없다 문제는 '*' 이 asterisk 문자다. 하지만 조건만 제대로 따져서 문제를 풀면 결코 어려운 문제가 아니다.

문제에서 preceding이라는 문구가 있다. 이것은 '*' 바로 직전에 문자를 가지고 매칭을 한다는 것이다. 'c*' 를 예로들면 "", "c", "cccc", "cc" 등 c가 얼마나 나와도 상관없이 매칭한다는 것이다.

그렇다면 아예 이 '*' 문자를 가지고 매칭을 하지 않아도 될 때는 p패턴의 인덱스를 2만큼 오른쪽으로 이동시켜 다시 매칭여부를 판별하면 된다.

하지만 매칭을 할 시에는 필수 조건이 있는데 바로 '*' 전에 s 문자열에서도 p문자열과 마찬가지고 매칭하고자하는 preceding 문자가 동일하게 있어야한다는 것이다.

그것을 구현한 코드가 바로 아래 코드다.

3. What I solved

class Solution {
public:
    int cache[1000][1000];
    bool isMatch(string s, string p) {
        memset(cache, -1, sizeof(cache));
        return match(0, 0, s, p);
    }
    
    bool match(int i, int j, const string& s, const string& p){
        if(cache[i][j] != -1)
            return cache[i][j];

        bool ans;
        if(j == p.size()){
            ans = i == s.size();
        }
        else {
            bool first_match = (i < s.size() && (s[i] == p[j] || p[j] =='.'));
            if(j + 1 < p.size() && p[j+1] == '*'){
                ans = match(i, j+2, s, p) || (first_match && match(i+1, j, s, p));
            }
            else {
                ans = first_match && match(i+1, j+1, s, p);
            }
        }
        cache[i][j] = ans ? 1 : 0;
        return ans;
    } 
};