当前位置:网站首页>[LeetCode] Wildcard Matching 外卡匹配
[LeetCode] Wildcard Matching 外卡匹配
2022-07-05 11:22:00 【全栈程序员站长】
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
这道题通配符匹配问题还是小有难度的,这道里用了贪婪算法Greedy Alogrithm来解,由于有特殊字符*和?,其中?能代替任何字符,*能代替任何字符串,那么我们需要定义几个额外的指针,其中scur和pcur分别指向当前遍历到的字符,再定义pstar指向p中最后一个*的位置,sstar指向此时对应的s的位置,具体算法如下:
– 定义scur, pcur, sstar, pstar
– 如果*scur存在
– 如果*scur等于*pcur或者*pcur为 ‘?’,则scur和pcur都自增1
– 如果*pcur为’*’,则pstar指向pcur位置,pcur自增1,且sstar指向scur
– 如果pstar存在,则pcur指向pstar的下一个位置,scur指向sstar自增1后的位置
– 如果pcur为’*’,则pcur自增1
– 若*pcur存在,返回False,若不存在,返回True
C 解法一:
bool isMatch(char *s, char *p) {
char *scur = s, *pcur = p, *sstar = NULL, *pstar = NULL;
while (*scur) {
if (*scur == *pcur || *pcur == '?') {
++scur;
++pcur;
} else if (*pcur == '*') {
pstar = pcur++;
sstar = scur;
} else if (pstar) {
pcur = pstar + 1;
scur = ++sstar;
} else return false;
}
while (*pcur == '*') ++pcur;
return !*pcur;
}
这道题也能用动态规划Dynamic Programming来解,写法跟之前那道题Regular Expression Matching很像,但是还是不一样。外卡匹配和正则匹配最大的区别就是在星号的使用规则上,对于正则匹配来说,星号不能单独存在,前面必须要有一个字符,而星号存在的意义就是表明前面这个字符的个数可以是任意个,包括0个,那么就是说即使前面这个字符并没有在s中出现过也无所谓,只要后面的能匹配上就可以了。而外卡匹配就不是这样的,外卡匹配中的星号跟前面的字符没有半毛钱关系,如果前面的字符没有匹配上,那么直接返回false了,根本不用管星号。而星号存在的作用是可以表示任意的字符串,当然只是当匹配字符串缺少一些字符的时候起作用,当匹配字符串包含目标字符串没有的字符时,将无法成功匹配。
C++ 解法二:
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size(), n = p.size();
vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
dp[0][0] = true;
for (int i = 1; i <= n; ++i) {
if (p[i - 1] == '*') dp[0][i] = dp[0][i - 1];
}
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++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[m][n];
}
};
类似题目:
参考资料:
https://discuss.leetcode.com/topic/3040/linear-runtime-and-constant-space-solution
https://discuss.leetcode.com/topic/40118/clear-c-dp-solution-similar-to-the-last-matching-problem
LeetCode All in One 题目讲解汇总(持续更新中…)
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/109497.html原文链接:https://javaforall.cn
边栏推荐
- Dspic33ep clock initialization program
- The art of communication III: Listening between people
- CDGA|数据治理不得不坚持的六个原则
- Array
- R3live series learning (IV) r2live source code reading (2)
- Characteristics and electrical parameters of DDR4
- Bidirectional RNN and stacked bidirectional RNN
- Question and answer 45: application of performance probe monitoring principle node JS probe
- The ninth Operation Committee meeting of dragon lizard community was successfully held
- 基础篇——REST风格开发
猜你喜欢
随机推荐
Lombok 同时使⽤@Data和@Builder 的坑,你中招没?
Differences between IPv6 and IPv4 three departments including the office of network information technology promote IPv6 scale deployment
DDoS attack principle, the phenomenon of being attacked by DDoS
基础篇——REST风格开发
[JS] extract the scores in the string, calculate the average score after summarizing, compare with each score, and output
Operators
An error is reported in the process of using gbase 8C database: 80000305, host IPS long to different cluster. How to solve it?
【爬虫】charles unknown错误
uniapp
Three suggestions for purchasing small spacing LED display
四部门:从即日起至10月底开展燃气安全“百日行动”
C # to obtain the filtered or sorted data of the GridView table in devaexpress
如何通俗理解超级浏览器?可以用于哪些场景?有哪些品牌?
华为设备配置信道切换业务不中断
无密码身份验证如何保障用户隐私安全?
Three paradigms of database
Deepfake tutorial
Oneforall installation and use
Paradigm in database: first paradigm, second paradigm, third paradigm
Home office things community essay