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.
READ MORE
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