LeetCode -- Wildcard Matching

题目描述：


Implement wildcard pattern matching with support for '?' and '*'.


'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).


The matching should cover the entire input string (not partial).


The function prototype should be:
bool isMatch(const char *s, const char *p)


Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false


实现字符串匹配。输入字符串s,和字符串匹配p，?可被替换为任何非空字符，*可替换空字符或任何字符。
设，arr[i,j]表示s的第i个字符是否和p的第j个字符匹配。对于s[i]和p[j]，分为三种情况：
arr[i,j] = arr[i-1,j-1] ,p[j]=?
arr[i,j] = arr[i-1,j-1] && s[i-1] == p[j-1] ，p[j]为普通字符
arr[i,j] = arr[i-1,j-1]||arr[i-1,j]||arr[i,j-1] ，p[j]为*


实现代码：

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 matchfor (var i = 0;i < s.Length; i++){dp[i+1,0] = false;}// pattern not empty, s is empty , not matchfor (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 matchdp[i,j] = dp[i-1,j-1] && s[i-1] == p[j-1];}}}//Console.WriteLine(dp);return dp[s.Length,p.Length];}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！