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.
1def isMatch(s, p):
2 memo = {}
3 def dfs(i, j):
4 if (i, j) in memo:
5 return memo[(i, j)]
6 if j == len(p):
7 return i == len(s)
8 match = i < len(s) and (s[i] == p[j] or p[j] == '.')
9 if (j + 1) < len(p) and p[j+1] == '*':
10 memo[(i, j)] = dfs(i, j + 2) or (match and dfs(i + 1, j))
11 return memo[(i, j)]
12 if match:
13 memo[(i, j)] = dfs(i + 1, j + 1)
14 return memo[(i, j)]
15 memo[(i, j)] = False
16 return False
17 return dfs(0, 0)The Python solution uses a depth-first search (DFS) approach with memoization to tackle overlapping subproblems. We check if characters at position i in the string and j in the pattern match directly or through special symbols. The '*' in the pattern is handled by either skipping it or considering it as multiple matches.
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#include <string>
using namespace std;
class Solution {
public:
bool isMatch(string s, string p) {
vector<vector<bool>> dp(s.size() + 1, vector<bool>(p.size() + 1, false));
dp[0][0] = true;
for (int j = 1; j < p.size(); ++j) {
if (p[j] == '*') {
dp[0][j + 1] = dp[0][j - 1];
}
}
for (int i = 0; i < s.size(); ++i) {
for (int j = 0; j < p.size(); ++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] && (s[i] == p[j - 1] || p[j - 1] == '.'));
}
}
}
return dp[s.size()][p.size()];
}
};This C++ solution leverages tabulation with a matrix employed to store states of string-pattern matches. It iteratively adjusts the table based on character conditions, managing '.' and '*' in the pattern for successful or unmatched cases.