当前位置：首页 > news >正文

LeetCode -- Wildcard Matching

news 来源：原创 2024/5/20 11:39:23

题目描述：

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