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

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

 

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

 

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);
}
};
请我喝杯咖啡吧~