首页 > 代码库 > Wildcard Matching

Wildcard Matching

2024-09-16 17:07:10   221人阅读

题目

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

方法

使用贪心的策略。使用两个变量：star——标记p字符串中*的位置， begin——标记s字符串中*匹配的的位置。
首先推断是否同样。假设同样i++，j++。

假设不同，则推断是否是*，记录begin 和 star值，j++。

假设不是*，依据star和begin。又一次匹配，begin++。
    public boolean isMatch(String s, String p) {
    	if ((s == null && p == null) || (s.length() == 0 && p.length() == 0)) {
    		return true;
    	}
    	int lenS = s.length();
    	int lenP = p.length();
    	int star = -1;
    	int begin = -1;
    	int i = 0;
    	int j = 0;
    	while (i < lenS) {
    		if (j < lenP && (s.charAt(i) == p.charAt(j) || p.charAt(j) == ‘?‘)) {
    			i++;
    			j++;
    		} else if (j < lenP && p.charAt(j) == ‘*‘){
    			star = j;
    			begin = i;
    			j++;
    		} else if (star != -1) {
    			j = star + 1;
    			i = begin + 1;
    			begin++;
    		} else {
    			return false;
    		}
    	}
    	while(j < lenP && p.charAt(j) == ‘*‘) {
    		j++;
    	}
    	return j == lenP;
    }


Wildcard Matching


联系
我们