当前位置:网站首页>Leetcode 44 Wildcard matching (2022.02.13)
Leetcode 44 Wildcard matching (2022.02.13)
2022-07-06 00:33:00 【ChaoYue_ miku】
Given a string (s) And a character pattern § , Implement a support ‘?’ and ‘*’ The wildcard matches .
‘?’ It can match any single character .
‘*’ Can match any string ( Include empty string ).
Only when two strings match exactly can the match be successful .
explain :
s May is empty , And contains only from a-z Lowercase letters of .
p May is empty , And contains only from a-z Lowercase letters of , As well as the character ? and *.
Example 1:
Input :
s = “aa”
p = “a”
Output : false
explain : “a” Can't match “aa” Whole string .
Example 2:
Input :
s = “aa”
p = ""
Output : true
explain : '’ Can match any string .
Example 3:
Input :
s = “cb”
p = “?a”
Output : false
explain : ‘?’ Can match ‘c’, But the second one ‘a’ Can't match ‘b’.
Example 4:
Input :
s = “adceb”
p = “ab”
Output : true
explain : first ‘’ Can match an empty string , the second '’ Can match string “dce”.
Example 5:
Input :
s = “acdcb”
p = “a*c?b”
Output : false
source : Power button (LeetCode)
link :https://leetcode-cn.com/problems/wildcard-matching
Method 1 : Dynamic programming
C++ Submission :
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size();
int n = p.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
dp[0][0] = true;
for (int i = 1; i <= n; ++i) {
if (p[i - 1] == '*') {
dp[0][i] = true;
}else {
break;
}
}
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (p[j - 1] == '*') {
dp[i][j] = dp[i][j - 1] | dp[i - 1][j];
}else if (p[j - 1] == '?' || s[i - 1] == p[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
}
}
}
return dp[m][n];
}
};
边栏推荐
- Ffmpeg learning - core module
- LeetCode 1598. Folder operation log collector
- Natural language processing (NLP) - third party Library (Toolkit):allenlp [library for building various NLP models; based on pytorch]
- 【DesignMode】装饰者模式(Decorator pattern)
- [EI conference sharing] the Third International Conference on intelligent manufacturing and automation frontier in 2022 (cfima 2022)
- LeetCode 6005. The minimum operand to make an array an alternating array
- OpenCV经典100题
- Determinant learning notes (I)
- STM32按键消抖——入门状态机思维
- Spark AQE
猜你喜欢
FFT learning notes (I think it is detailed)
Extracting profile data from profile measurement
建立时间和保持时间的模型分析
Model analysis of establishment time and holding time
notepad++正则表达式替换字符串
Search (DFS and BFS)
How to use the flutter framework to develop and run small programs
Intranet Security Learning (V) -- domain horizontal: SPN & RDP & Cobalt strike
Room cannot create an SQLite connection to verify the queries
Arduino六足机器人
随机推荐
Introduction of motor
[designmode] composite mode
Date类中日期转成指定字符串出现的问题及解决方法
Free chat robot API
Intranet Security Learning (V) -- domain horizontal: SPN & RDP & Cobalt strike
Ffmpeg learning - core module
[Online gadgets] a collection of online gadgets that will be used in the development process
Common API classes and exception systems
OpenCV经典100题
Location based mobile terminal network video exploration app system documents + foreign language translation and original text + guidance records (8 weeks) + PPT + review + project source code
NLP generation model 2017: Why are those in transformer
Single source shortest path exercise (I)
Leetcode:20220213 week race (less bugs, top 10% 555)
Extracting profile data from profile measurement
[EI conference sharing] the Third International Conference on intelligent manufacturing and automation frontier in 2022 (cfima 2022)
从底层结构开始学习FPGA----FIFO IP核及其关键参数介绍
小程序技术优势与产业互联网相结合的分析
MDK debug时设置数据实时更新
Spark AQE
Priority queue (heap)