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.
1public class Solution {
2 public boolean isMatch(String s, String p) {
3 Boolean[][] memo = new Boolean[s.length() + 1][p.length() + 1];
4 return dfs(0, 0, s, p, memo);
5 }
6 private boolean dfs(int i, int j, String s, String p, Boolean[][] memo) {
7 if (memo[i][j] != null) {
8 return memo[i][j];
9 }
10 if (j == p.length()) {
11 return i == s.length();
12 }
13 boolean match = i < s.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');
14 if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
15 memo[i][j] = dfs(i, j + 2, s, p, memo) || (match && dfs(i + 1, j, s, p, memo));
16 return memo[i][j];
17 }
18 if (match) {
19 memo[i][j] = dfs(i + 1, j + 1, s, p, memo);
20 return memo[i][j];
21 }
22 memo[i][j] = false;
23 return false;
24 }
25}The Java solution employs a DFS strategy enhancing it with memoization via a Boolean matrix to avoid recomputation. For each (i, j) pair of the string and pattern, we decide if they match, handle '*' by skipping it or proceeding in the string.
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.
1The Python DP solution constructs a 2D boolean array where dp[i][j] signifies if the first i characters of the string match the first j characters of the pattern. The matrix is initialized with the base conditions and filled based on the characters in pattern string, iteratively updating for mismatches dictated by '*' or '.'.