LeetCode #44: Wildcard Matching

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

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

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

Note:

• s could be empty and contains only lowercase letters a-z.
• p could be empty and contains only lowercase letters a-z, and characters like ? or *.

Example 1:

Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input:
s = "aa"
p = "*"
Output: true
Explanation: '*' matches any sequence.

Example 3:

Input:
s = "cb"
p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.

Example 4:

Input:
s = "adceb"
p = "*a*b"
Output: true
Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".

Example 5:

Input:
s = "acdcb"
p = "a*c?b"
Output: false

Solution:

• DP (2d) method with a 2d matrix containing the boolean values.
• The first row and the first column should be considered carefully.
• A minimum required length array is needed for the first column.
• Time complexity: O(m*n)
• Space complexity: O(m*n)

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        if len(p) == 0:
            if len(s) == 0: return True
            else: return False
        else:
            if len(s) == 0:
                if ''.join(set(p)) == '*': return True
                else: return False
            else:
                flag = [[False for y in s] for x in p]                
                minlen = [0]    # minimum required length of string s
                for x in p:
                    if x == '*': minlen.append(minlen[-1])
                    else: minlen.append(minlen[-1] + 1)
                minlen.pop(0)

                # first row
                if p[0] == '*':  
                    flag[0] = [True for y in s]
                else: 
                    if (s[0] == p[0]) or (p[0] == '?'): flag[0][0] = True                    

                for i in range(1, len(p)):
                    # first column
                    if (p[i] in ['*', '?', s[0]]) and flag[i-1][0] and (minlen[i] <= 1): flag[i][0] = True
                    for j in range(1, len(s)):
                        if ('a'<=p[i]<='z' and flag[i-1][j-1] and (p[i] == s[j])) or \
                            (p[i] == '?' and flag[i-1][j-1]) or \
                            (p[i] == '*' and (flag[i-1][j-1] or flag[i-1][j] or flag[i][j-1])):
                            flag[i][j] = True

                return flag[-1][-1]