public class Solution { public bool IsMatch(string s, string p) { var dp = new bool[s.Length + 1, p.Length + 1]; dp[0,0] = true; // s is empty , pattern is empty, match // s is not empty , patter is empty , not match for (var i = 0;i < s.Length; i++){ dp[i+1,0] = false; } // pattern not empty, s is empty , not match for (var i = 0;i < p.Length; i++){ dp[0, i+1] = p[i] == '*' && dp[0, i]; } for (var i = 1; i <= s.Length; i++){ for (var j = 1;j <= p.Length; j++){ if (p[j-1] == '?'){ dp[i,j] = dp[i-1,j-1]; // depends on previous match or no } else if(p[j-1] == '*'){ // 1. ab a* // 2. bavfdc b* // pattern j matches string i - 1 (* is any char) // or // pattern j-1 matches string i (* can be removed) //Console.WriteLine(i+","+j); dp[i,j] = dp[i-1,j] || dp[i, j-1] || dp[i-1,j-1]; } else{ // pattern is a normal charactor , previous match also current char should match dp[i,j] = dp[i-1,j-1] && s[i-1] == p[j-1]; } } } //Console.WriteLine(dp); return dp[s.Length,p.Length]; }}
新闻热点
疑难解答