Given an input string (`s`

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

**Example 1:**

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

**Example 2:**

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

**Example 3:**

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

**Example 4:**

Input:s = "aab", p = "c*a*b"Output:trueExplanation:c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".

**Example 5:**

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

**Constraints:**

`0 <= s.length <= 20`

`0 <= p.length <= 30`

`s`

contains only lowercase English letters.`p`

contains only lowercase English letters,`'.'`

, and`'*'`

.- It is guaranteed for each appearance of the character
`'*'`

, there will be a previous valid character to match.

public boolean isMatch(String s, String p) {
if(s == null || p == null){
return false;
}
boolean[][] dp = new boolean[p.length()+1][s.length()+1];
for(int i=0;i<dp.length;i++){
for(int j=0;j<dp[0].length;j++){
if(i==0 && j==0){
dp[i][j] = true;
}
else if(i==0){
dp[i][j] = false;
}
else if(j==0){
char pc = p.charAt(i-1);
if(pc == '*'){
dp[i][j] = dp[i-2][j];
}
}
else{
char sc = s.charAt(j-1);
char pc = p.charAt(i-1);
if(pc=='*'){
char ppc = p.charAt(i-2);
dp[i][j] = dp[i-2][j];
if(!dp[i][j] && (ppc == sc || ppc=='.')){
dp[i][j] = dp[i][j-1];
}
}
else if(pc=='.'){
dp[i][j] = dp[i-1][j-1];
}
else if(sc == pc){
dp[i][j] = dp[i-1][j-1];
}
}
}
}
return dp[p.length()][s.length()];
}

This is one of the top questions we should be solving in Dynamic Programming. The basic idea is to break the bigger task into smaller tasks and keep track of already solved tasks and re-use the result.

Time Complexity: O(m*n) // where m and n are the lengths of string and patterns

Space Complexity: O(m*n)