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
和Regular Expression Matching很像,这里的'?'相当于Regular Expression中的'.',但'*'的用法不一样。这里'*'与前一个字符没有联系,并且无法消去前一个字符,但可以表示任意一串字符。递推公式的推导和Regular Expression Matching也基本类似。
p[j-1] == s[i-1] || p[j-1] == '?':dp[i][j] = dp[i-1][j-1]
p[j-1] == '*':
1. 匹配0个字符:dp[i][j] = dp[i][j-1]
2. 匹配1个字符:dp[i][j] = dp[i-1][j-1]
3. 匹配多个字符:dp[i][j] = dp[i-1][j]
先用二维数组写,发现会Memory Limit Exceeded
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | class Solution { public: bool isMatch(const char *s, const char *p) { int m = strlen(s), n = strlen(p); vector<vector<bool>> dp(m+1, vector<bool>(n+1,false)); dp[0][0] = true; for(int i=0; i<m; i++) { for(int j=1; j<n; j++) { if(p[j-1]==s[i-1] || p[j-1]=='?') dp[i][j] = i>0 && dp[i-1][j-1]; else if(p[j-1]=='*') dp[i][j] = dp[i][j-1] || (i>0 && (dp[i-1][j-1] || dp[i-1][j])); } } return dp[m][n]; } }; |
然后用一维滚动数组改写,发现会Time Limit Exceeded
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | class Solution { public: bool isMatch(const char *s, const char *p) { int m = strlen(s), n = strlen(p); vector<bool> dp(m+1, false); for(int i=0; i<m; i++) { bool diag = dp[0]; dp[0] = i==0 ? true : false; for(int j=1; j<n; j++) { int temp = dp[j]; if(p[j-1]==s[i-1] || p[j-1]=='?') dp[j] = i>0 && diag; else if(p[j-1]=='*') dp[j] = dp[j-1] || (i>0 && (diag || dp[j])); diag = temp; } } return dp[n]; } }; |
用DP会TLE,那么一定有其他好的方法。
前辈你好,我目前也开始边刷题边用博客记录,想请教你是如何在blogspot上使用markdown编排文档的?搜了很久也没发现合适的方法。感谢🙏
ReplyDelete没弄明白为什么:匹配多个字符:dp[i][j] = dp[i-1][j]
ReplyDeleteJames 大哥:
Delete其实可以写成大致
else if(p[j-1]=='*')
dp[i][j] = dp[i][j-1] || dp[i-1][j] ;
其中 dp[i][j-1] 是处理 * 号当成空串用;
dp[i-1][j] 是处理 * 当成非空串用,这里的递归思路是 text 的最大前缀串已经匹配 pattern 目前的带有 * 的完整串,也就是说 text 的当前比较的最后那个字符只是个“无关紧要的摆设而已;因为 * 可以是任意内容,任意长度。