当前位置:网站首页>[leetcode] wild card matching
[leetcode] wild card matching
2022-07-05 11:28:00 【Full stack programmer webmaster】
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
The wildcard matching problem of this problem is still a little difficult , Greedy algorithm is used in this road Greedy Alogrithm To solve , Because of the special characters * and ?, among ? Can replace any character ,* Can replace any string , Then we need to define several additional pointers , among scur and pcur Respectively point to the currently traversed characters , Redefine pstar Point to p Last of * The location of ,sstar Point to the corresponding s The location of , The specific algorithm is as follows :
– Definition scur, pcur, sstar, pstar
– If *scur There is
– If *scur be equal to *pcur perhaps *pcur by ‘?’, be scur and pcur All increase by themselves 1
– If *pcur by ’*’, be pstar Point to pcur Location ,pcur Self increasing 1, And sstar Point to scur
– If pstar There is , be pcur Point to pstar Next position of ,scur Point to sstar Self increasing 1 The back position
– If pcur by ’*’, be pcur Self increasing 1
– if *pcur There is , return False, If it does not exist , return True
C Solution 1 :
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;
}
This problem can also be solved by dynamic programming Dynamic Programming To solve , The writing method is the same as the previous question Regular Expression Matching It's like , But it's still different . The biggest difference between wild card matching and regular matching is in the rules of using asterisks , For regular matching , The asterisk cannot exist alone , It must be preceded by a character , The meaning of the asterisk is to indicate that the number of characters in front of it can be any , Include 0 individual , That is to say, even if the previous character is not in s It doesn't matter if it appears in , As long as the latter can match . This is not the case with external card matching , The asterisk in the wild card matching has nothing to do with the previous character , If the preceding characters do not match , Then go straight back false 了 , Never mind the asterisk . The function of the asterisk is to represent any string , Of course, it only works when the matching string is missing some characters , When the matching string contains characters that the target string does not , Will not match successfully .
C++ Solution 2 :
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];
}
};
Similar topics :
Reference material :
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 Summary of topic explanation ( Ongoing update …)
Publisher : Full stack programmer stack length , Reprint please indicate the source :https://javaforall.cn/109497.html Link to the original text :https://javaforall.cn
边栏推荐
- DDRx寻址原理
- 高校毕业求职难?“百日千万”网络招聘活动解决你的难题
- 7 大主题、9 位技术大咖!龙蜥大讲堂7月硬核直播预告抢先看,明天见
- NFT 交易市场主要使用 ETH 本位进行交易的局面是如何形成的?
- 购买小间距LED显示屏的三个建议
- OneForAll安装使用
- [there may be no default font]warning: imagettfbbox() [function.imagettfbbox]: invalid font filename
- What does cross-border e-commerce mean? What do you mainly do? What are the business models?
- 无密码身份验证如何保障用户隐私安全?
- COMSOL -- establishment of 3D graphics
猜你喜欢
[JS] extract the scores in the string, calculate the average score after summarizing, compare with each score, and output
不要再说微服务可以解决一切问题了!
Three suggestions for purchasing small spacing LED display
[advertising system] incremental training & feature access / feature elimination
Cdga | six principles that data governance has to adhere to
[crawler] Charles unknown error
数据库三大范式
R3live series learning (IV) r2live source code reading (2)
技术管理进阶——什么是管理者之体力、脑力、心力
【爬虫】wasm遇到的bug
随机推荐
Zcmu--1390: queue problem (1)
7 themes and 9 technology masters! Dragon Dragon lecture hall hard core live broadcast preview in July, see you tomorrow
7.2 daily study 4
Cdga | six principles that data governance has to adhere to
NFT 交易市场主要使用 ETH 本位进行交易的局面是如何形成的?
如何通俗理解超级浏览器?可以用于哪些场景?有哪些品牌?
【Office】Excel中IF函数的8种用法
COMSOL--三维图形的建立
idea设置打开文件窗口个数
go语言学习笔记-分析第一个程序
What about SSL certificate errors? Solutions to common SSL certificate errors in browsers
[crawler] Charles unknown error
Four departments: from now on to the end of October, carry out the "100 day action" on gas safety
Solve the grpc connection problem. Dial succeeds with transientfailure
C language current savings account management system
DDR4的特性与电气参数
comsol--三维图形随便画----回转
2048游戏逻辑
Repair animation 1K to 8K
龙蜥社区第九次运营委员会会议顺利召开