# Wildcard Matching Leetcode – Python Solution

LeetCode has a Hard coding Problem in Its’ Algorithm Section “Wildcard Matching Leetcode”. Today We are going to solve this problem in Python. LeetCode Link of the Problem is HERE.

#### Question

Given an input string (`s`) and a pattern (`p`), implement wildcard pattern matching with support for `'?'` and `'*'` where:

• `'?'` Matches any single character.
• `'*'` Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

Examples

Input: s = “aa”, p = “a” Output: false

Explanation: “a” does not match the entire string “aa”.

Input: s = “aa”, p = “*” Output: true

Explanation: ‘*’ matches any sequence.

Input: s = “cb”, p = “?a” Output: false

Explanation: ‘?’ matches ‘c’, but the second letter is ‘a’, which does not match ‘b’.

#### Constraints

• `0 <= s.length, p.length <= 2000`
• `s` contains only lowercase English letters.
• `p` contains only lowercase English letters, `'?'` or `'*'`.

#### Solution to “Wildcard Matching Leetcode”

``````class Solution(object):
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
i = 0
j = 0
match = 0
starIdx = -1
while (i < len(s)):
if (j < len(p) and (p[j] == '?' or s[i] == p[j])):
i+=1
j+=1
elif (j < len(p) and p[j] == '*'):
starIdx = j
match = i
j+=1

elif (starIdx != -1):
j = starIdx + 1
match+=1
i = match
else:
return False
while (j < len(p) and p[j] == '*'):
j+=1

return j == len(p)``````

Success:

Runtime: 68 ms, faster than 90.24% of Python online submissions for Wildcard Matching.
Memory Usage: 13.5 MB, less than 94.67% of Python online submissions for Wildcard Matching.

Python-related posts Visit HERE

C++ related posts Visit HERE

Databases related posts Visit HERE

Data Structures related posts visit HERE

Algorithms related posts visit HERE

Data Science related posts visit HERE

Share the Knowledge