# C# DP O(n2) regular Expression match and wild card match

• ``````//wildcard match
public class Solution {
public bool IsMatch(string s, string p) {
//2D DP
int m=s.Length,n=p.Length;
bool[,] DP=new bool[m+1,n+1];
DP[0,0]=true;
for(int j=1;j<=n;j++)
{
if(p[j-1]=='*'&&DP[0,j-1])
DP[0,j]=true;
}

for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if (p[j-1]!='*') {
DP[i,j] = DP[i-1,j-1] && (s[i-1]==p[j-1] || p[j-1]=='?');
} else {
DP[i,j] = DP[i-1,j] || DP[i,j-1];
}
}
}

return DP[m,n];
}
}
``````

//regular expression match

``````public class Solution {
public bool IsMatch(string s, string p) {
//2D DP
int m=s.Length,n=p.Length;
bool[,] DP=new bool[m+1,n+1];
DP[0,0]=true;
for(int j=1;j<=n;j++)
{
if(p[j-1]=='*')
{
if(DP[0,j-1]||(j>1&&DP[0,j-2]))
DP[0,j]=true;
}
}

for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(s[i-1]==p[j-1]||p[j-1]=='.')
DP[i,j]=DP[i-1,j-1];
if(p[j-1]=='*')
{
if(p[j-2]==s[i-1]||p[j-2]=='.')
DP[i,j]=DP[i-1,j]||DP[i,j-1]||DP[i,j-2];
else
DP[i,j]=DP[i,j-2];
}
}
}

return DP[m,n];
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.