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.
Given an input string (
s) and a pattern (
p), implement wildcard pattern matching with support for
'?'Matches any single character.
'*'Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).
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’.
0 <= s.length, p.length <= 2000
scontains only lowercase English letters.
pcontains only lowercase English letters,
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)
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