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];

    }
};