given an input string (s) and a pattern (p), implement wildcard patterning matching with support for “?” and “*” where “?” matches any single character and “*” matches any sequence of characters in python

main.py
def isMatch(s: str, p: str) -> bool:
    # Initialize indices for string and pattern
    s_index, p_index = 0, 0
    # Initialize indices for * in pattern and index of * in string
    star_index, match_index = -1, 0
        
    # Iterate through string
    while s_index < len(s):
        # If the current characters match or the pattern has a ?,
        # move both indices to the right
        if p_index < len(p) and (p[p_index] == '?' or s[s_index] == p[p_index]):
            s_index += 1
            p_index += 1
        # If the pattern has a *, store its index and the current string index
        elif p_index < len(p) and p[p_index] == '*':
            star_index = p_index
            match_index = s_index
            p_index += 1
        # If the current pattern character is not a * but the indices stored
        # by * are not -1, reset the indices
        elif star_index != -1:
            p_index = star_index + 1
            match_index += 1
            s_index = match_index
        # If none of the above conditions are met, return False
        else:
            return False
    
    # Once we reach the end of the string, check if any characters in the
    # remaining pattern are not *
    while p_index < len(p) and p[p_index] == '*':
        p_index += 1
    
    # Return True if we have reached the end of both the string and pattern,
    # False otherwise
    return p_index == len(p)
1417 chars
37 lines

We can test our function as follows:

main.py
s = "leetcode"
p = "*t?co*de"
print(isMatch(s, p))   # Expected output: True

s = "aaa"
p = "a*a"
print(isMatch(s, p))   # Expected output: True

s = "acdcb"
p = "a*c?b"
print(isMatch(s, p))   # Expected output: False
218 chars
12 lines

gistlibby LogSnag