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

Start with the foundation – the base cases, which are the simplest solutions. Then, layer by layer, use the results of the previous layers to calculate the solutions for the next level. This way, we systematically build up the entire solution, avoiding redundant calculations and ensuring efficiency. It is like building a pyramid.

The underlying calculation logic remains fundamentally identical to the original recursive approach, albeit executed in reverse order.

# Python implementation

def match(t, p):
  cache = [[False for _ in range(len(p) + 1)] for _ in range(len(t) + 1)]

  cache[0][0] = True

  for i in range(1, len(p) + 1):
    if p[i - 1] == '*' and i > 1:
      cache[0][i] = cache[0][i - 2]

  for i in range(1, len(t) + 1):
    for j in range(1, len(p) + 1):          
      if p[j - 1] == t[i - 1] or p[j - 1] == '.':
        cache[i][j] = cache[i - 1][j - 1]
      elif p[j - 1] == '*' and j > 1:
        cache[i][j] = cache[i][j - 2] or ((p[j - 2] == t[i - 1] or p[j - 2] == '.') and cache[i - 1][j])

  return cache[len(t)][len(p)]

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

print(match(text, pattern))

// Javascript implementation

function match(t, p) {
  const cache = Array.from(Array(t.length + 1), () => Array(p.length + 1).fill(false));

  cache[0][0] = true;

  for (let i = 1; i < p.length + 1; i++) {
    if (p[i - 1] == '*' && i > 1) {
      cache[0][i] = cache[0][i - 2];
    }
  }

  for (let i = 1; i < t.length + 1; i++) {
    for (let j = 1; j < p.length + 1; j++) {          
      if (p[j - 1] == t[i - 1] || p[j - 1] == '.') {
        cache[i][j] = cache[i - 1][j - 1];
      } else if (p[j - 1] == '*' && j > 1) {
        cache[i][j] = cache[i][j - 2] || ((p[j - 2] == t[i - 1] || p[j - 2] == '.') && cache[i - 1][j]);
      }
    }
  }

  return cache[t.length][p.length];
}

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

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

Regular expression wildcard pattern matching (Tabulation)

Hint