Sponsored
Sponsored
The dynamic programming approach uses a 2D table to store results of subproblems. We define dp[i][j] as True if the first i characters in the string s can be matched by the first j characters of the pattern p.
Base Cases:
Fill the table using the following rules:
Time Complexity: O(m*n) where m and n are the lengths of s and p, respectively.
Space Complexity: O(m*n) due to the storage of the dp table.
1def isMatch(s: str, p: str) -> bool:
2 m, n = len(s), len(p)
3 dp = [[False] * (n + 1) for _ in range(m + 1)]
4 dp[0][0] = True
5
6 for j in range(1, n + 1):
7 if p[j - 1] == '*':
8 dp[0][j] = dp[0][j - 1]
9
10 for i in range(1, m + 1):
11 for j in range(1, n + 1):
12 if p[j - 1] == '*':
13 dp[i][j] = dp[i - 1][j] or dp[i][j - 1]
14 elif p[j - 1] == '?' or s[i - 1] == p[j - 1]:
15 dp[i][j] = dp[i - 1][j - 1]
16
17 return dp[m][n]
18This Python implementation also adopts the 2D DP table approach. Here, the dp list-of-lists encapsulates the match possibilities, similar to other languages' implementations.
The greedy algorithm approach tracks the position of the last '*' in the pattern and attempts to match remaining characters greedily. We maintain two pointers, one for the string and one for the pattern. When encountering '*', we remember the positions of both pointers in order to backtrack if needed.
If characters in p and s match or if the pattern has '?', both pointers are incremented. For '*', we shift the pattern pointer and remember indices for future potential matches. If there's a mismatch after '*', we use these remembered indices to backtrack.
Time Complexity: O(m + n) due to possible backtracking
Space Complexity: O(1) requiring constant storage for indices.
This greedy algorithm utilizes backtracking facilitated by the last seen '*' position to handle mismatches, allowing us to efficiently manage sequences that can contain many wildcard characters.