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.
1var isMatch = function(s, p) {
2 const m = s.length;
3 const n = p.length;
4 const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(false));
5 dp[0][0] = true;
6
7 for (let j = 1; j <= n; j++) {
8 if (p[j - 1] === '*') {
9 dp[0][j] = dp[0][j - 1];
10 }
11 }
12
13 for (let i = 1; i <= m; i++) {
14 for (let j = 1; j <= n; j++) {
15 if (p[j - 1] === '*') {
16 dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
17 } else if (p[j - 1] === '?' || s[i - 1] === p[j - 1]) {
18 dp[i][j] = dp[i - 1][j - 1];
19 }
20 }
21 }
22 return dp[m][n];
23};
24This JavaScript solution leverages a 2D array to simulate the dynamic programming matrix. The matching logic mirrors the logic employed in the other languages.
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.