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 at the end, compare the last character of the pattern and the last character of the text:

Continue this process recursively until the pattern becomes empty, then check if text is empty. If the text is empty but the last two characters of the pattern ends with '*', remove them from the pattern and try again.

# Python implementation

def match(t, p):
  if len(p) == 0:
    return len(t) == 0

  if len(t) == 0:
    return (p[-1] == '*' and len(p) >= 2) and match(t, p[0:-2])

  if t[-1] == p[-1] or p[-1] == '.':
    return match(t[0:-1], p[0:-1])

  if 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)

    return zero or more
  
  return False

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

print(match(text, pattern))

// Javascript implementation

function match(t, p) {
  if (p.length === 0) {
    return t.length === 0;
  }

  if (t.length === 0) {
    return (p.at(-1) === '*' && p.length >= 2) && match(t, p.slice(0, -2));
  }

  if (t.at(-1) === p.at(-1) || p.at(-1) === '.') {
    return match(t.slice(0, -1), p.slice(0, -1));
  }

  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);

    return zero || more;
  }
  
  return false;
}

const text = 'helloworld';
const pattern = 'hel*oworl.';

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

Regular expression wildcard pattern matching

Hint