Regular expression wildcard pattern matching (Memoization)

Given a text and a pattern, test if pattern matches text. Both text and pattern consist of only lowercase alphabets while pattern also consists special characters of "." and "*". "." matches any single character and "*" matches zero or more of the preceding character.

Hint

This algorithm uses memoization to improve performance. It's same as the recursive version of Regular expression wildcard pattern matching, but with a special 'cache' to store results. The 'cache key' is crucial. It's how we identify and store past results. Sometimes we need one key, sometimes multiple keys. We add code to:

• Initialize cache to store results.
• Using the key to check cached result. If the result is not found in the cache, do the calculation and save the result in cache.
• Return the cached result.

• Python
• Javascript
•  Run

cache = {}

def match(t, p):
  if t not in cache:
    cache[t] = {}

  if p not in cache[t]:
    cache[t][p] = False
    
    if len(p) == 0:
      cache[t][p] = len(t) == 0
    elif len(t) == 0:
      cache[t][p] = (p[-1] == '*' and len(p) >= 2) and match(t, p[0:-2])
    elif t[-1] == p[-1] or p[-1] == '.':
      cache[t][p] = match(t[0:-1], p[0:-1])
    elif p[-1] == "*" and len(p) > 1:
      zero = match(t, p[0:-2])
      more = (p[-2] == t[-1] or p[-2] == '.') and match(t[0:-1], p)
      cache[t][p] = zero or more
  
  return cache[t][p]

text = "helloworld"
pattern = "hel*oworl."

print(match(text, pattern))

const cache = {}

function match(t, p) {
  if (cache[t] === undefined) {
    cache[t] = {}
  }

  if (cache[t][p] === undefined) {
    cache[t][p] = false
    
    if (p.length === 0) {
      cache[t][p] = t.length === 0;
    } else if (t.length === 0) {
      cache[t][p] = (p.length >= 2 && p.at(-1) === '*') && match(t, p.slice(0, -2));
    } else if (t.at(-1) === p.at(-1) || p.at(-1) === '.') {
      cache[t][p] = match(t.slice(0, -1), p.slice(0, -1));
    } else if (p.at(-1) === "*" && p.length > 1) {
      let zero = match(t, p.slice(0, -2));
      let more = (p.at(-2) == t.at(-1) || p.at(-2) === '.') && match(t.slice(0, -1), p);
      
      cache[t][p] = zero || more;
    }
  }
  
  return cache[t][p];
}

const text = "helloworld"
const pattern = "hel*oworl."

console.log(match(text, pattern));