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
96
97
98
99
100
101
102
103
104
105
106
107
108
/**
 * Determine if a text string matches a given pattern with support for '.' and '*'.
 * @param {string} text - The input text string
 * @param {string} pattern - The pattern to match against
 * @return {boolean} - True if the text matches the pattern, false otherwise
 */
function isMatch(text, pattern) {
  // Create a memoization map
  const memo = new Map();
  
  function match(i, j) {
    // Create a unique key for the current state
    const key = i + ',' + j;
    
    // Check if we've already computed this result
    if (memo.has(key)) {
      return memo.get(key);
    }
    
    // Base case: if we've reached the end of the pattern
    if (j === pattern.length) {
      return i === text.length;
    }
    
    // Check if the current characters match
    const firstMatch = i < text.length && 
      (pattern[j] === text[i] || pattern[j] === '.');
    
    // If the next character is '*'
    if (j + 1 < pattern.length && pattern[j + 1] === '*') {
      // Either skip the pattern character and '*' (match zero occurrences)
      // or match the current character and continue with the same pattern
      const result = match(i, j + 2) || 
        (firstMatch && match(i + 1, j));
      
      memo.set(key, result);
      return result;
    } else {
      // If the current characters match, move to the next characters
      const result = firstMatch && match(i + 1, j + 1);
      
      memo.set(key, result);
      return result;
    }
  }
  
  return match(0, 0);
}
 
/**
 * Dynamic Programming approach to determine if a text string matches a given pattern.
 * @param {string} text - The input text string
 * @param {string} pattern - The pattern to match against
 * @return {boolean} - True if the text matches the pattern, false otherwise
 */
function isMatchDP(text, pattern) {
  const m = text.length;
  const n = pattern.length;
  
  // Create a DP table
  const dp = Array(m + 1).fill().map(() => Array(n + 1).fill(false));
  
  // Empty pattern matches empty text
  dp[0][0] = true;
  
  // Handle patterns like a*, b*, etc. which can match empty string
  for (let j = 1; j <= n; j++) {
    if (pattern[j - 1] === '*') {
      dp[0][j] = dp[0][j - 2];
    }
  }
  
  // Fill the DP table
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (pattern[j - 1] === '*') {
        // Either ignore the pattern character and its preceding element
        dp[i][j] = dp[i][j - 2];
        
        // Or if the current text character matches the preceding pattern character,
        // use the result from dp[i-1][j]
        if (pattern[j - 2] === '.' || pattern[j - 2] === text[i - 1]) {
          dp[i][j] = dp[i][j] || dp[i - 1][j];
        }
      } else {
        // If the current characters match, use the result from dp[i-1][j-1]
        if (pattern[j - 1] === '.' || pattern[j - 1] === text[i - 1]) {
          dp[i][j] = dp[i - 1][j - 1];
        }
      }
    }
  }
  
  return dp[m][n];
}
 
// Test cases
console.log(isMatch("aab", "c*a*b"));  // true
console.log(isMatch("mississippi", "mis*is*p*."));  // false
console.log(isMatch("ab", ".*"));  // true
console.log(isMatch("", ".*"));  // true
console.log(isMatch("aaa", "a*a"));  // true
 
console.log(isMatchDP("aab", "c*a*b"));  // true
console.log(isMatchDP("mississippi", "mis*is*p*."));  // false
console.log(isMatchDP("ab", ".*"));  // true
console.log(isMatchDP("", ".*"));  // true
console.log(isMatchDP("aaa", "a*a"));  // true