C# solution: 2D dp with explanation


  • 0
    B

    For example:
    aab aac

    create a dp[4,4]

    Find out the rule of * and letter first

    T = true
    F = false
    empty a * a * c
    empty T F F F F F
    a F T T F F F
    a F F T T T F
    b F F T F T F

    ? is easy, just like this: if (p[pIndex] == '?' || s[sIndex] == p[pIndex])

    public class Solution 
    {
        public bool IsMatch(string s, string p) 
        {
            var sLength = s.Length;
            var pLength = p.Length;
    
            var dp = new bool[sLength + 1, pLength + 1];
    
            dp[0, 0] = true;
    
            for (int j = 1; j < p.Length + 1; j++)
            {
                var pIndex = j - 1;
                if (p[pIndex] != '*')
                {  
                    dp[0, j] = false;
                }
                else
                {
                    dp[0, j] = dp[0, j - 1];
                }
            }
    
            for (int i = 1; i < sLength + 1; i++)
            {
                var sIndex = i - 1;
                for (int j = 1; j < pLength + 1; j++)
                {
                    var pIndex = j - 1;
                    if (p[pIndex] == '*')
                    {
                        dp[i, j] = dp[i, j - 1] || dp[i - 1, j];
                    }
                    else
                    {
                        if (p[pIndex] == '?' || s[sIndex] == p[pIndex])
                        {
                            dp[i, j] = dp[i - 1, j - 1];
                        }
                    }
                }
            }
    
            return dp[sLength, pLength];
        }
    }
    

Log in to reply
 

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