Given an input string s&nbsp;and a pattern p, implement regular expression matching with support for '.' and '*' where:


	'.' Matches any single character.​​​​
	'*' Matches zero or more of the preceding element.


The matching should cover the entire input string (not partial).

&nbsp;
Example 1:

Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".


Example 2:

Input: s = "aa", p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".


Example 3:

Input: s = "ab", p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".


&nbsp;
Constraints:


	1 &lt;= s.length&nbsp;&lt;= 20
	1 &lt;= p.length&nbsp;&lt;= 30
	s contains only lowercase English letters.
	p contains only lowercase English letters, '.', and&nbsp;'*'.
	It is guaranteed for each appearance of the character '*', there will be a previous valid character to match.


class Solution:
   def isMatch(self, s, p):
       n = len(s)
       m = len(p)
       dp = [[False for _ in range (m+1)] for _ in range (n+1)]
       dp[0][0] = True
       for c in range(1,m+1):
           if p[c-1] == '*' and c > 1:
               dp[0][c] = dp[0][c-2]
       for r in range(1,n+1):
           for c in range(1,m+1):
               if p[c-1] == s[r-1] or p[c-1] == '.':
                   dp[r][c] = dp[r-1][c-1]
               elif c > 1 and p[c-1] == '*':
                   if  p[c-2] =='.' or s[r-1]==p[c-2]:
                       dp[r][c] =dp[r][c-2] or dp[r-1][c]
                   else:
                       dp[r][c] = dp[r][c-2]
       return dp[n][m]
class Solution {
    public boolean isMatch(String s, String p) {
        if (p == null || p.length() == 0) return (s == null || s.length() == 0);

        boolean dp[][] = new boolean[s.length()+1][p.length()+1];
        dp[0][0] = true;
        for (int j=2; j<=p.length(); j++) {
            dp[0][j] = p.charAt(j-1) == '*' && dp[0][j-2];
        }

        for (int j=1; j<=p.length(); j++) {
            for (int i=1; i<=s.length(); i++) {
                if (p.charAt(j-1) == s.charAt(i-1) || p.charAt(j-1) == '.')
                    dp[i][j] = dp[i-1][j-1];
                else if(p.charAt(j-1) == '*')
                    dp[i][j] = dp[i][j-2] || ((s.charAt(i-1) == p.charAt(j-2) || p.charAt(j-2) == '.') && dp[i-1][j]);
            }
        }
        return dp[s.length()][p.length()];
    }
}
class Solution {
public:
    bool isMatch(string s, string p) {
        return helper(s,p,0,0);
    }
    
    bool helper(string s, string p, int i, int j)
    {
        if(j==p.length())
            return i==s.length();
        bool first_match=(i<s.length() && (s[i]==p[j] || p[j]=='.' ));
        
        if(j+1<p.length() && p[j+1]=='*')
        {
            return (helper(s,p,i,j+2)|| (first_match && helper(s,p,i+1,j) ));
        }
        else
        {
            return (first_match && helper(s,p,i+1,j+1));
        }
    }
};
/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */

var isMatch = function(s, p) {
    const pattern = new RegExp('^'+p+'$'); // ^ means start of string, $ means end of the string, these are to prevent certain pattern that match a part of the string to be returned as true.
    return pattern.test(s);
};
Regular Expression Matching