# 10. Regular Expression Matching

Given a string (s) and a character pattern (p). Implementation supports regular expression matching of '.' and '*'.

```'. Matches any single character.
'*' matches zero or more preceding elements.
```

The match should cover the entire string (s), not part of the string.

Explain:

• s may be empty and contain only lowercase letters from a-z.
• p may be empty and contain only lowercase letters from a-z, as well as the characters. And *.

Example 1:

```Input:
s = "aa"
p = "a"
Output: false
Explanation: 'a' cannot match the entire string of 'aa'.
```

Example 2:

```Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means that zero or more preceding elements can be matched, that is, 'a' can be matched. Therefore, repeat 'a' once and the string can be changed to 'aa'.
```

Example 3:

```Input:
s = "ab"
p = ".*"
Output: true
Explanation: ". *" means that zero or more ('*') arbitrary characters ('.') can be matched.
```

Example 4:

```Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: 'c' may not be repeated, and 'a' may be repeated once. So you can match the string "aab.".
```

Example 5:

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

① Recursive solution

```static const auto x = [](){
ios::sync_with_stdio(false);
cin.tie(NULL);
return NULL;
}();

class Solution {
public:
bool isMatch(string s, string p) {
//If p is empty, it depends on whether s is empty. If s is empty, it returns true. If it is not empty, it returns false
if(p.empty()) return s.empty();
//To see what the second character of p is, if it is * then it depends on whether the first character of p is needed or not, if so, it requires s not to be empty, p matches the first character of S, and the string after s starts from the second must match p
//If you don't want to, just round off the first character of p and see if p doesn't match s from the third character
if(p[1] == '*')
return isMatch(s, p.substr(2)) || !s.empty() && (p[0] == s[0] || p[0] == '.') && isMatch(s.substr(1), p);
else//If the second character of p is not * then the first character of p and s must match and S is not empty and the substrings after s and p must match
return !s.empty() && (p[0] == s[0] || p[0] == '.') && isMatch(s.substr(1), p.substr(1));

}
};```

② Dynamic programming solution

```static const auto x = [](){
ios::sync_with_stdio(false);
cin.tie(NULL);
return NULL;
}();

class Solution {
public:
bool isMatch(string s, string p) {
int n = s.length(), m = p.length();
//dp[i][j] indicates whether s[0...i] matches p[0...j]
vector<vector<bool>> dp(n + 1, vector<bool>(m + 1, false));
dp[0][0] = true;//Null match null returns true
dp[0][1] = false;//Null matching a character is absolutely false
for(int i = 1; i <= n; ++i)//i characters match null is also false
{
dp[i][0] = false;
}
for(int j = 2; j <= m; ++j)//See what the second character of p is. If it is' * ', then the true and false values of dp[0][j] are the same as dp[0][j-2]
{
dp[0][j] = dp[0][j-2] && p[j-1] == '*';
}

for(int j = 1; j <= m; ++j)//Iterate from the length of p, when the length of p is j
{
for(int i = 1; i <= n; ++i)//For s of length i
{
if(p[j-1] == '*')//If p the previous character of the current character is' * '
{
//s:abc p:abc * in two cases, s and p (remove the end of c *) match or directly match with p
dp[i][j] = dp[i][j-2]  || dp[i-1][j] && (s[i-1] == p[j-2] || p[j-2] == '.');
}
else//s: AB c P: ab port must have c = = port
{
dp[i][j] = dp[i-1][j-1] && (p[j-1] == s[i-1] || p[j-1] == '.');
}
}
}
return dp[n][m];

}
};```

Keywords: iOS Programming

Added by tablex on Tue, 07 Jan 2020 17:43:21 +0200