# 10. Regular Expression Matching 正则表达式匹配

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).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true
``````

Difficulty: Hard

## 分析1

• 匹配串往后移动1位,模式串跳过`'*'`
• 匹配串往后移动1位,模式串不动
• 匹配串不动,模式串跳过`'*'`
``````class Solution {
public:
bool isMatch(string s, string p) {
const char* str = s.c_str();
const char* pattern = p.c_str();
return match2(str, pattern);
}

bool match2(const char* str,const char* pattern)
{
if (str==NULL||pattern==NULL) return false;
if (*str=='\0'&&*pattern=='\0') return true;
if (*str!='\0'&&*pattern=='\0') return false;

if (*(pattern+1)=='*')
{
if (*str==*pattern||(*str!='\0'&&*pattern=='.'))
return match2(str+1, pattern+2)||match2(str+1, pattern)||match2(str, pattern+2);
return match2(str, pattern+2);
}
if (*str==*pattern || (*pattern=='.'&&*str!='\0'))
return match2(str+1, pattern+1);
return false;
}
};
``````

## 分析2

• `P[i][j] = P[i-1][j-1]`,if `p[j-1] != '*' && (s[i-1] == p[j-1] || p[j-1] == '.')`;
• `P[i][j] = P[i][j-2]`,if `p[j-1]=='*'` and the pattern repeats for `0` times;
• `P[i][j] = P[i-1][j] && (s[i-1]==p[j-2] || p[j-2]=='.')`,if `p[j-1]=='*'` and the pattern repeats for at least `1` times.

``````s = "ab";
p = "ab";
P[0][0] = s[0,0)j[0,0) = true
P[1][1] = s[0,1)p[0,1) = s[0]p[0] = ('a'=='a') = true
``````
``````class Solution {
public:

bool isMatch(string s, string p)
{
int m = s.size(), n = p.size();
vector<vector<bool>> dp(m+1,vector<bool>(n+1,false));
dp[0][0] = true;
for (int i = 0; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (p[j-1] == '*')
dp[i][j] = dp[i][j-2] || (i > 0 && (s[i-1]==p[j-2] || p[j-2]=='.') && dp[i-1][j]);
else
dp[i][j] = i > 0 && dp[i-1][j-1] && (s[i-1]==p[j-1]||p[j-1]=='.');
}
}
return dp[m][n];
}
``````