细语呢喃

技术改变生活

0%

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

方法1：递归

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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版本正着写一直很慢。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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

 

方法2：动态规划

设 dp[i][j] 为字符串 s 的前 i 个字符和 p 的前 j 个字符能否匹配，设都为空串的时候dp[0][0] = true;

  • 如果s[i - 1] == p[j - 1]||p[j - 1] == '.' ||，说明为小写字符且相等，或者由于通配符可以直接匹配，则dp[i][j] = dp[i - 1][j - 1]

  • 如果p[j - 1] == '*'：

    • 则如果不重复前一个字符，为dp[i][j - 2]
    • 如果重复前一个字符,则需要s[i - 1] == p[j - 1] || p[j - 1] == '.'，此时要匹配，说明为dp[i - 1][j]也需要匹配（相当于舍弃s[i - 1]，仍然匹配）

初始条件：

在实际实现中，为了防止越界，实际将字符串的下标移动了一下，当i = 1的时候，是s[0]的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size();
        int n = p.size();
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
        dp[0][0] = true;
        for (int j = 2; j <= n ; ++j) {
            if (p[j - 1] == '*') {
                dp[0][j] = dp[0][j - 2];
            }
        }

        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p[j - 1] == '*') {
                    if (j >= 2)
                        dp[i][j] = dp[i][j - 2];
                    if (j >= 2 && (p[j - 2] == s[i - 1] || p[j - 2] == '.')) {
                        dp[i][j] = dp[i][j] || dp[i - 1][j];
                    }
                } else if (p[j - 1] == '.' || p[j - 1] == s[i - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
        return dp[m][n];
    }
};

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++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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]

 

没有滚动数组优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool isMatch(string s, string p) {
        vector<vector<bool>> dp(s.size() + 1, vector<bool>(p.size() + 1, false));
        dp[0][0] = true;
        for (int j = 1; j <= p.size(); ++j) {
            if (p[j - 1] == '*')
                dp[0][j] = dp[0][j - 1];
        }
        for (int i = 1; i <= s.size(); ++i) {
            for (int j = 1; j <= p.size(); ++j) {
                if (p[j - 1] == '*') {
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                } else {
                    dp[i][j] = (s[i - 1] == p[j - 1] || p[j - 1] == '?') && dp[i - 1][j - 1];
                }
            }
        }
        return dp[s.size()][p.size()];
    }
};

C++ 递归TLE版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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);
	}
};
请我喝杯咖啡吧~