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”, “c*a*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”, “c*a*b”) → false
题目地址：leetcode Wildcard Matching
题目大意：和上面一题类似，?表示匹配任何字符，*表示匹配任意字符串序列，给定s和p，问是否匹配。
和上面一题的最大区别在于，*不在表示前面一个字符，而是可以变成任意字符串序列。
学着上面一题的思路，写了个递归，TLE ! 想到连续的几个*和一个是一样的！于是改了，依然TLE!
然后用dp了。
dp[i][j]为前i个s和前j p是否匹配。
则有：
- p[j]==’*’ dpi][j]=dp[i-1][j] || dp[i][j-1] (*要么匹配当前的，要么不匹配）
- 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); } }; |
本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处：细语呢喃 > leetcode Regular Expression Matching || leetcode Wildcard Matching
本文地址：https://www.hrwhisper.me/leetcode-regular-expression-matching-leetcode-wildcard-matching/
第一个python 代码 有个数组越界的情况 就是p=‘*’ 的时候，取不到p[:-2]，leetcode 测试代码有漏洞 要加一段代码
if len(p)==1:
if len(s)!=1:
return False
if p[0]!=’.’ and p[0]!=s[0]:
return False
return True