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.
1#include <stdbool.h>
2#include <string.h>
3
4bool isMatch(char * s, char * p) {
5 int m = strlen(s);
6 int n = strlen(p);
7 bool dp[m + 1][n + 1];
8 memset(dp, false, sizeof(dp));
9 dp[0][0] = true;
10 for (int j = 1; j <= n; j++) {
11 if (p[j - 1] == '*') dp[0][j] = dp[0][j - 1];
12 }
13 for (int i = 1; i <= m; i++) {
14 for (int j = 1; j <= n; j++) {
15 if (p[j - 1] == '*') {
16 dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
17 } else {
18 dp[i][j] = dp[i - 1][j - 1] && (p[j - 1] == '?' || s[i - 1] == p[j - 1]);
19 }
20 }
21 }
22 return dp[m][n];
23}
24The code initializes a boolean matrix dp such that dp[i][j] is True if the first i characters of s match with the first j characters of p.
We handle '*' using two cases: either it matches the empty sequence, so we look to the left; or it matches one or more characters, so we look above.
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.