# leetcode Regular Expression Matching || leetcode Wildcard Matching

### 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

aab和c*a*b为true时因为，p中第一个*代替0个c，第二个*代替两个a，于是可以变为aab，和s相同，所以为true

If the next character of p is NOT ‘*’, then it must match the current character of s. Continue pattern matching with the next character of both s and p.
If the next character of p is ‘*’, then we do a brute force exhaustive matching of 0, 1, or more repeats of current character of p… Until we could not match any more characters.

C++

Python版本正着写一直很慢。。

### 44. Wildcard Matching

Implement wildcard pattern matching with support for `'?'` and `'*'`.

‘?’ Matches any single character.
‘*’ Matches any sequence of characters (including the empty sequence).

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”, “*”) → true
isMatch(“aa”, “a*”) → true
isMatch(“ab”, “?*”) → true
isMatch(“aab”, “c*a*b”) → false

dp[i][j]为前i个s和前j p是否匹配。

1. p[j]==’*’  dpi][j]=dp[i-1][j] || dp[i][j-1]  (*要么匹配当前的，要么不匹配）
2. p[j] ≠’*’   dp[i][j]=dp[i-1][j-1]  (当然，p[j-1]==s[j-1] || p[j-1]==’?’ )

C++

Python

C++ 递归TLE版：