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


  • 0
    Y
    //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];
        }
    }

Log in to reply
 

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