---
# System prepended metadata

title: leetcode 10.Regular Expression Matching

---

# leetcode 10.Regular Expression Matching

* 二維dp
* ```dp[i][j]``` 為```s[0:i]```跟```p[0:j]```的比對結果
* 當```s[i-1]==p[j-1] || p[j-1]=='.'```時，就看了個都去掉時也能不能配對。
* 當```p[i]='*'```時，兩種可能
    1. 重複0次，所以直接往後兩格取
    2. 重複>1次，則```s[i] == p[j-1] || p[j-1] == '.' ```，同時```dp[i-1][j]```(s[i]去掉)也要能配對，因為i-1前的配對成功那i才有可能配對。 
* i=0（s為空字串）時另外比對（下面第7行）。如果正規表達式p有字的話那每個字元一定要配上一個```*```，因為星號可以重複零次。因此星號一定在```p[2*n-1]```的位置（字母＋星號兩兩一組）。

```cpp=
class Solution {
public:
    bool isMatch(string s, string p) {
        int n=s.size(), nn=p.size();
        vector<vector<int>> dp(n+1, vector<int>(nn+1, 0));
        dp[0][0]=1;
        for(int i=2;i<=nn && p[i-1]=='*';i+=2)
            dp[0][i]=1;
        for(int i=1;i<=n;++i){
            for(int j=1;j<=nn;++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] || ((s[i-1]==p[j-2] || p[j-2]=='.') && dp[i-1][j]);
                else
                    dp[i][j]=0;
            }
        }
        //for(auto i:dp){
            //for(auto j:i){
                //cout << j << " ";
            //}
            //cout << "\n";
        //}
        return dp[n][nn];

    }
};  
```

* 類似題：longest common subsequence, edit distance