当前位置:网站首页>[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
边栏推荐
- Cron表达式(七子表达式)
- DDR4硬件原理图设计详解
- [Oracle] use DataGrid to connect to Oracle Database
- [SWT component] content scrolledcomposite
- [advertising system] parameter server distributed training
- 分类TAB商品流多目标排序模型的演进
- shell脚本文件遍历 str转数组 字符串拼接
- Cdga | six principles that data governance has to adhere to
- Codeforces Round #804 (Div. 2)
- Redis如何实现多可用区?
猜你喜欢
How can China Africa diamond accessory stones be inlaid to be safe and beautiful?
购买小间距LED显示屏的三个建议
pytorch训练进程被中断了
[office] eight usages of if function in Excel
Three suggestions for purchasing small spacing LED display
[crawler] Charles unknown error
7.2 daily study 4
7 themes and 9 technology masters! Dragon Dragon lecture hall hard core live broadcast preview in July, see you tomorrow
In the last process before the use of the risk control model, 80% of children's shoes are trampled here
【爬虫】wasm遇到的bug
随机推荐
技术分享 | 常见接口协议解析
FreeRTOS 中 RISC-V-Qemu-virt_GCC 的调度时机
uboot的启动流程:
[advertising system] incremental training & feature access / feature elimination
go语言学习笔记-初识Go语言
C#实现WinForm DataGridView控件支持叠加数据绑定
管理多个Instagram帐户防关联小技巧大分享
DDR4的特性与电气参数
7 大主题、9 位技术大咖!龙蜥大讲堂7月硬核直播预告抢先看,明天见
Unity Xlua MonoProxy Mono代理类
Prevent browser backward operation
POJ 3176-Cow Bowling(DP||记忆化搜索)
[there may be no default font]warning: imagettfbbox() [function.imagettfbbox]: invalid font filename
COMSOL--建立几何模型---二维图形的建立
An error is reported in the process of using gbase 8C database: 80000305, host IPS long to different cluster. How to solve it?
Evolution of multi-objective sorting model for classified tab commodity flow
C # to obtain the filtered or sorted data of the GridView table in devaexpress
C language current savings account management system
COMSOL--三维图形的建立
Three paradigms of database