LeetCode 44. Wildcard Matching | Wildcard Matching LeetCode | Wildcard Matching Dynamic Programming

⚡️My Courses on Udemy:

🈚️ BEST RESOURCES FOR SOFTWARE ENGINEERING PREP

📝Statement: Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'.
1. '?' Matches any single character.
2. '*' Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).
Note:
# s could be empty and contains only lowercase letters a-z.
# p could be empty and contains only lowercase letters a-z, and characters like ? or *.

✅️BEST RESOURCES FOR SOFTWARE ENGINEERING PREP

✅️EQUIPMENT I USED IN THIS VIDEO:

✴️PRACTICE CODING QUESTIONS

❇️FREE RESOURCE ONLINE

⚡ Please leave a LIKE and SUBSCRIBE for more content! ⚡

⭐ Tags ⭐
- LeetCode
- Software Engineering
- Wildcard Matching
- Dynamic Programming
- LeetCode 44. Wildcard Matching
- Wildcard Matching Leetcode
- LeetCode Wildcard Matching
- Wildcard Matching Dynamic Programming
- Algorithms
- Programming
- Coding

⭐ Hashtags ⭐
#leetcode

Disclosure: Some links are affiliate links to products. I may receive a small commission for purchases made through these links. #csninja

[savarchaturvedi]

if s is zero and there is pattern (*)then the value should be true but who have written false.
cell[0][4] is false but should be true.

[wpraagavendran]

you have to slightly change the code because this code doesn't work for string = "aa", pattern = "*";

modified code

for (int i = 0; i <= s_len; i++) {
for (int j = 0; j <= p_len; j++) {
if (i == 0 && j == 0) {
dp[i][j] = true;
}
else if (i == 0) {

if (dp[i][j-1] == true && p.charAt(j-1) == '*') {
dp[i][j] = true;
}
else {
dp[i][j] = false;
}
}
else if (i != 0 && j == 0) {
dp[i][j] = false;
}
else if (s.charAt(i-1) == p.charAt(j-1) || p.charAt(j-1) == '?') {
dp[i][j] = dp[i-1][j-1];
}
else if (p.charAt(j-1) == '*'){
dp[i][j] = dp[i][j-1] || dp[i-1][j];
}
}
}

[jiaweiwu]

Such a clear and great video. Thanks so much!

[edwardteach]

I think there's a typo in the if statement when checking for the '?'
Shouldn't s[j-1] == '?' be p[j-1] == '?', since our p is the pattern and we can find the '?' in the p string?

Overall everything is good, here's my Python implementation:

class Solution(object):
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
N = len(s)
M = len(p)

dp = [[False] * (M + 1) for _ in range(N + 1)]
dp[0][0] = True

for j in range(1, M + 1):
if p[j-1] == "*":
dp[0][j] = True
else:
break

for i in range(1, N + 1):
for j in range(1, M + 1):
if s[i-1] == p[j-1] or p[j-1] == "?":
dp[i][j] = dp[i-1][j-1]
elif p[j-1] == "*":
dp[i][j] = dp[i-1][j] or dp[i][j-1]

return dp[N][M]

[usemayonaise]

Doesn't work if the pattern starts with *

[DrewRanger]

You are trying so hard to hide your Bengali accent with as much American as possible, I could not focus on your approach :)

[Pradeep-ihzh]

Can you share the source code using Python?

[Code_G]

bro u dont have to do the accent man...