当前位置:网站首页>[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
边栏推荐
- 爬虫(9) - Scrapy框架(1) | Scrapy 异步网络爬虫框架
- The ninth Operation Committee meeting of dragon lizard community was successfully held
- Solve the problem of slow access to foreign public static resources
- 解决readObjectStart: expect { or n, but found N, error found in #1 byte of ...||..., bigger context ..
- Empêcher le navigateur de reculer
- 阻止浏览器后退操作
- An error is reported in the process of using gbase 8C database: 80000305, host IPS long to different cluster. How to solve it?
- DDRx寻址原理
- go语言学习笔记-分析第一个程序
- 7 themes and 9 technology masters! Dragon Dragon lecture hall hard core live broadcast preview in July, see you tomorrow
猜你喜欢
随机推荐
Stop saying that microservices can solve all problems!
Sklearn model sorting
[first release in the whole network] (tips for big tables) sometimes it takes only 1 minute for 2 hours of SQL operation
ibatis的动态sql
Ddrx addressing principle
How to understand super browser? What scenarios can it be used in? What brands are there?
管理多个Instagram帐户防关联小技巧大分享
SLAM 01. Modeling of human recognition Environment & path
Cron表达式(七子表达式)
Lombok makes ⽤ @data and @builder's pit at the same time. Are you hit?
[advertising system] parameter server distributed training
Detailed explanation of MATLAB cov function
comsol--三维图形随便画----回转
How can China Africa diamond accessory stones be inlaid to be safe and beautiful?
Modulenotfounderror: no module named 'scratch' ultimate solution
What does cross-border e-commerce mean? What do you mainly do? What are the business models?
Mysql统计技巧:ON DUPLICATE KEY UPDATE用法
以交互方式安装ESXi 6.0
Empêcher le navigateur de reculer
Basics - rest style development