leetcode Regular Expression Matching || leetcode Wildcard Matching

10. Regular Expression Matching

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character. '*' Matches zero or more of the preceding element.

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", "a") → true isMatch("aa", ".") → true isMatch("ab", ".") → true isMatch("aab", "ca*b") → true

题目地址：leetcode Regular Expression Matching

题意：'.'表示可以代替任何字符，*表示可以代替前面一个出现的字符，且可以代表任意个，给定字符串s和p，问s和p是否匹配。

aab和c*a*b为true时因为，p中第一个*代替0个c，第二个*代替两个a，于是可以变为aab，和s相同，所以为true

If the next character of p is NOT *, then it must match the current character of s. Continue pattern matching with the next character of both s and p. If the next character of p is *, then we do a brute force exhaustive matching of 0, 1, or more repeats of current character of p... Until we could not match any more characters

C++

class Solution {
private:
	bool do_match(size_t i, size_t j, const string &s, const string &p) {
		if (p.size() <= j) return s.size() <= i;

		if (j + 1 < p.size() && p[j + 1] == '*') {
			for (; i < s.size() && (s[i] == p[j] || p[j] == '.'); i++) {
				if (do_match(i, j + 2, s, p)) return true;
			}
			return do_match(i, j + 2, s, p);
		}
		else {
			if (p[j] == '.' && i < s.size() || p[j] == s[i]) return do_match(i + 1, j + 1, s, p);
			return false;
		}
	}

public:
	bool isMatch(string s, string p) {
		return do_match(0, 0, s, p);
	}
};

Python版本正着写一直很慢。。

class Solution:
    # @return a boolean   
    def isMatch(self,s,p):
        if not p:
            return not s           
        if p[-1]=='*':
            if len(p)==1:
                return False
            if self.isMatch(s, p[:-2]):    
                return True               
            if s and (s[-1]==p[-2] or p[-2]=='.'):
                return self.isMatch(s[:-1], p)           
        else:
            if s and (s[-1]==p[-1] or p[-1]=='.'):
                return self.isMatch(s[:-1], p[:-1] )
        return False

 

44. 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", "ca*b") → false

题目地址：leetcode Wildcard Matching

题目大意：和上面一题类似，?表示匹配任何字符，*表示匹配任意字符串序列，给定s和p，问是否匹配。

和上面一题的最大区别在于，*不在表示前面一个字符，而是可以变成任意字符串序列。

学着上面一题的思路，写了个递归，TLE ! 想到连续的几个*和一个是一样的！于是改了，依然TLE!

然后用dp了。

dp[i][j]为前i个s和前j p是否匹配。

则有：

1. p[j]=='*'  dpi][j]=dp[i-1][j] dp[i][j-1]  (*要么匹配当前的，要么不匹配）
2. p[j] ≠'*'   dp[i][j]=dp[i-1][j-1]  (当然，p[j-1]==s[j-1] p[j-1]=='?')

记得用两个一维数组即可，o(n*m）空间会超内存T^T。

嗯，还有就是要做一个剪枝，p长度为m，s长度为n，设p中'*'个数为cnt，如果n-cnt > m，显然无解。

C++

class Solution {
public:
	bool isMatch(const char *s, const char *p) {
		int m = strlen(s);
		int n = strlen(p);
		int cnt = count(p, p + n, '*');
		if (n - cnt > m)  return false;
		vector<bool> dp(n + 1, false);
		dp[0] = 1;
		for (int j = 1; j <= n; j++) if (p[j - 1] == '*') dp[j] = dp[j - 1];
		for (int i = 1; i <= m; i++)
		{
			vector<bool> cur (n + 1, false);
			for (int j = 1; j <= n; j++)
			{
				if (p[j - 1] == '*'){
					cur[j] = dp[j] || cur[j - 1];
				}
				else{
					if (s[i - 1] == p[j - 1] || p[j - 1] == '?')
						cur[j] = dp[j - 1];
				}
			}
			dp = cur;
		}
		return dp[n];
	}
};

Python

class Solution:
    # @param s, an input string
    # @param p, a pattern string
    # @return a boolean
    def isMatch(self, s, p):
        m,n = len(s),len(p)
        cnt =p.count('*')
        if n - cnt > m:
            return False
        
        dp=[True] + [False]*n

        for j in range(1,n+1):
            dp[j]= dp[j-1] and p[j-1]=='*'
        
        for i in range(1,m+1):
            cur=[False]*(n+1)
            for j in range(1,n+1):
                if p[j-1]=='*':
                    cur[j]= cur[j-1] or dp[j]
                elif p[j-1]==s[i-1] or p[j-1]=='?':                   
                    cur[j]=dp[j-1]   
            dp=cur
        return dp[n]

 

C++ 递归TLE版：

class Solution {
public:
	bool judge(const char *s, const char *p){
		if (*p == '\0') return *s == '\0';
		if (*p == '*'){
			while (*p == '*') ++p;
			while (*s != '\0'){
				if (judge(s, p))
					return true;
				s++;
			}
			return judge(s, p);
		}
		else{
			if (*s == *p || *p == '?')
				return judge(s + 1, p + 1);
			else
				return false;
		}
		return false;
	}
	
	bool isMatch(const char *s, const char *p) {
		int m = strlen(s), n = strlen(p);
		int cnt = count(p, p + n, '*');
		if (n - cnt > m) return false;
		return judge(s, p);
	}
};