C# solution: 2D dp with explanation

• 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];
}
}
``````

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