Sponsored
Sponsored
This approach uses recursion with memoization to solve the problem efficiently. We recursively compare characters of the input string and the pattern, addressing special characters like '.' and '*'. The memoization is used to store results of sub-problems to avoid redundant calculations, which drastically improves the performance.
Time Complexity: O(m * n), where m and n are the lengths of the string and pattern, respectively. We solve every subproblem once and store the result.
Space Complexity: O(m * n) due to recursion stack and memoization storage.
1#include <stdbool.h>
2#include <string.h>
3
4bool dfs(int i, int j, const char* s, const char* p, int* memo, int slen, int plen) {
5 if (memo[i * (plen + 1) + j] != -1) {
6 return memo[i * (plen + 1) + j];
7 }
8 if (j == plen) {
9 return i == slen;
10 }
11 bool match = i < slen && (s[i] == p[j] || p[j] == '.');
12 if ((j + 1) < plen && p[j + 1] == '*') {
13 memo[i * (plen + 1) + j] = dfs(i, j + 2, s, p, memo, slen, plen) || (match && dfs(i + 1, j, s, p, memo, slen, plen));
14 return memo[i * (plen + 1) + j];
15 }
16 if (match) {
17 memo[i * (plen + 1) + j] = dfs(i + 1, j + 1, s, p, memo, slen, plen);
18 return memo[i * (plen + 1) + j];
19 }
20 memo[i * (plen + 1) + j] = false;
21 return false;
22}
23
24bool isMatch(const char* s, const char* p) {
25 int slen = strlen(s);
26 int plen = strlen(p);
27 int* memo = (int*)malloc((slen + 1) * (plen + 1) * sizeof(int));
28 for (int i = 0; i <= slen; ++i) {
29 for (int j = 0; j <= plen; ++j) {
30 memo[i * (plen + 1) + j] = -1;
31 }
32 }
33 bool result = dfs(0, 0, s, p, memo, slen, plen);
34 free(memo);
35 return result;
36}The C solution mirrors the same approach using an integer array as a memoization structure to track computation results. The recursive function matches characters from the string and pattern, considering '.' and '*', and returns the results casually.
This approach involves using a DP table to solve the problem by filling up a boolean matrix iteratively. This avoids recursion and stacks overhead, improving performance in certain scenarios. Each cell in the table represents whether the substring of the pattern matches the substring of the input.
Time Complexity: O(m * n) since we traverse the complete matrix.
Space Complexity: O(m * n) due to the DP table used to store subproblem solutions.
1 public bool IsMatch(string s, string p) {
var dp = new bool[s.Length + 1, p.Length + 1];
dp[0, 0] = true;
for (int j = 1; j < p.Length; j++) {
if (p[j] == '*') {
dp[0, j + 1] = dp[0, j - 1];
}
}
for (int i = 0; i < s.Length; i++) {
for (int j = 0; j < p.Length; j++) {
if (p[j] == '.' || s[i] == p[j]) {
dp[i + 1, j + 1] = dp[i, j];
} else if (p[j] == '*') {
dp[i + 1, j + 1] = dp[i + 1, j - 1] || (dp[i, j + 1] && (p[j - 1] == s[i] || p[j - 1] == '.'));
}
}
}
return dp[s.Length, p.Length];
}
}C# implementation of the DP tabulation augments a matrix to store the relationship between the string and the pattern. By dynamically adjusting the table in successive passes, it uses precedents while addressing symbols '.' and '*' specially.