1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
function isMatch(text, pattern) {
  // Create DP table
  const m = text.length;
  const n = pattern.length;
  const dp = Array(m + 1).fill().map(() => Array(n + 1).fill(false));
  
  // Empty text matches empty pattern
  dp[0][0] = true;
  
  // Empty text can match pattern with '*'
  for (let j = 1; j <= n; j++) {
    if (pattern[j - 1] === '*') {
      dp[0][j] = dp[0][j - 1];
    }
  }
  
  // Fill the DP table
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (pattern[j - 1] === '*') {
        // Match zero characters or one or more characters
        dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
      } else if (pattern[j - 1] === '?' || pattern[j - 1] === text[i - 1]) {
        // Match single character
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = false;
      }
    }
  }
  
  return dp[m][n];
}
 
// Alternative recursive approach with memoization
function isMatchRecursive(text, pattern) {
  // Memoization cache
  const memo = new Map();
  
  function match(i, j) {
    // Create a unique key for the current state
    const key = i + ',' + j;
    
    // If we've already computed this state, return the cached result
    if (memo.has(key)) {
      return memo.get(key);
    }
    
    // Base cases
    if (j === pattern.length) {
      return i === text.length;
    }
    
    if (i === text.length) {
      // Remaining pattern must be all '*'
      for (let k = j; k < pattern.length; k++) {
        if (pattern[k] !== '*') {
          return false;
        }
      }
      return true;
    }
    
    let result;
    
    // Current character in pattern
    if (pattern[j] === '*') {
      // Match zero characters
      result = match(i, j + 1);
      
      // If not matched, try matching one or more characters
      if (!result) {
        result = match(i + 1, j);
      }
    } else if (pattern[j] === '?' || pattern[j] === text[i]) {
      // Match single character
      result = match(i + 1, j + 1);
    } else {
      result = false;
    }
    
    // Cache the result
    memo.set(key, result);
    return result;
  }
  
  return match(0, 0);
}
 
// Test cases
console.log(isMatch("urgent-meeting", "urgent*"));  // true
console.log(isMatch("quarterly-report", "*report"));  // true
console.log(isMatch("budget-2023", "budget-??23"));  // true
console.log(isMatch("team-meeting", "team-*ing"));  // true
console.log(isMatch("project-update", "progress-*"));  // false