Wildcard Matching, Leetcode 解题笔记

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

Leetcode中最难的题之一,不过很多人onsite还是遇到了这道题,所以还是有必要掌握的。
一个比较好的算法是贪心算法(greedy): whenever encounter ‘*’ in p, keep record of the current position of ‘*’ in p and the current index in s. Try to match the stuff behind this ‘*’ in p with s, if not matched, just s++ and then try to match again.

public class WildcardMatching {
	public boolean isMatch(String s, String p) {
		int i = 0;
		int j = 0;
		int star = -1;
		int mark = -1;
		while (i < s.length()) {
			if (j < p.length()
					&& (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i))) {
				++i;
				++j;
			} else if (j < p.length() && p.charAt(j) == '*') {
				star = j;
                j++;
				mark = i;
           //这一步是关键,匹配s中当前字符与p中‘*’后面的字符,如果匹配,则在第一个if中处理,如果不匹配,则继续比较s中的下一个字符。
			} else if (star != -1) {
				j = star + 1;
				i = ++mark;
			} else {
				return false;
			}
		}
       //最后在此处处理多余的‘*’,因为多个‘*’和一个‘*’意义相同。
		while (j < p.length() && p.charAt(j) == '*') {
			++j;
		}
		return j == p.length();
	}
}

此题如果写成递归会因为循环而超时,以下是一个C++代码,用来展示其思路:

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        char cs = *s;
        char cp = *p;
        if(cp == '\0') {
            return cs == cp;
        } else if (cp == '?') {
            if (cs == '\0') return false;
            return isMatch(s + 1,p + 1);
        } else if (cp == '*') {
            const char *st = s;
            for(; *st != '\0'; ++st) {
                if (isMatch(st, p+1)) return true;
            }
            return isMatch(st,p+1);
        } else if (cp != cs)
            return false;
        return isMatch(s + 1,p + 1);
    }
};
Advertisements

2 thoughts on “Wildcard Matching, Leetcode 解题笔记

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s