[leetcode] 10. Regular Expression Matching

문제

Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.'.' Matches any single character. '*' Matches zero or more of the preceding element.

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

Note:

• s could be empty and contains only lowercase letters a-z.
• p could be empty and contains only lowercase letters a-z, and characters like . or *.

 

풀이

동적계획법(Dynamic Programming)을 이용한다.

$sl, pl$을 각각 $s, p$의 길이라고 하자. 그 후 $f$를 다음과 같이 정의한다.

$f(si, pi) =$ ( $s[si:]$와 $p[pi:]$가 matching 되는지의 여부)

 

그러면 다음과 같은 경우로 나눌수 있다.

case 1) $pi==pl$인 경우

이 경우에는 다음 패턴이 존재하지 않으므로 현재의 s와 완벽히 매칭이 되어야 한다.

 

case 2) $p[pi+1]$이 '*'이 아닌 경우

이 경우는 $s[si]$와 $p[pi]$가 매칭되면서 $f(si+1, pi+1)$이 참이면 $f(si,pi)$도 참이 된다.

나머지 경우에는 뒤쪽이 안맞거나 현재가 안 맞으므로 거짓이 된다.

 

case 3) $p[pi+1]$이 '*'인 경우

이 경우는 $s[i]$가 없을 수도, 여러개 나올 수도 있다.

s[i]가 없이 매칭되는 경우는 $f(si, pi+2)$가 된다. ('?*'를 제거)

s[i]가 있으면서 매칭되는 경우는 $s[si]$와 $p[pi]$가 매칭되면서 $f(si+1, pi)$가 참이어야 $f(si,pi)$가 참이 된다.

 

위 세가지 경우가 존재하는 모든 경우며 이를 이용해서 동적계획법을 구현하면 된다.

 

Time Complexity : $O(|S||P|)$

 

코드

class Solution {
private:
    vector< vector<int> > dp;
    int sl, pl;
    string S, P;
public:
    bool isMatch(string s, string p) {
        S=s, P=p;
        sl=s.length(), pl=p.length();
        
        dp.resize(sl+1);
        for(int i=0;i<=sl;i++)dp[i].resize(pl+1,-1);
        return f(0,0);
    }
    
    bool f(int si, int pi)
    {
        if(si>sl)return false;
        int& ret=dp[si][pi];
        if(dp[si][pi]!=-1) return ret;

        if(pi==pl) return ret=(si==sl)?1:0;
        bool match = (si<sl && (P[pi] == S[si] || P[pi]=='.'));
        if(pi+1<pl && P[pi+1]=='*')
            return ret = f(si, pi+2) || (match && f(si+1,pi));
        return ret = f(si+1, pi+1) && match;
    }
};