Wildcard Matching Leetcode – Python Solution

by

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

Share the Knowledge