首页 > 学院 > 开发设计 > 正文

LeetCode -- Wildcard Matching

2019-11-08 02:10:49
字体:
来源:转载
供稿:网友
题目描述: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") → falseisMatch("aa","aa") → trueisMatch("aaa","aa") → falseisMatch("aa", "*") → trueisMatch("aa", "a*") → trueisMatch("ab", "?*") → trueisMatch("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 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];    }}
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表