Regular Expression Matching

Problem

Match the whole string s against the pattern p where . matches any single character and * means zero or more of the preceding element.

Use dynamic programming: on a star either skip the whole pattern pair or consume one matching character from s, otherwise a literal or dot consumes one character from each. Return True only when the entire string matches.

Hint

A star always applies to the single element immediately before it, so skip two pattern characters when taking zero.

Test cases

case 1

in: ["aa","a"]

expected: false

case 2

in: ["aa","a*"]

expected: true

case 3

in: ["ab",".*"]

expected: true

case 4

in: ["aab","c*a*b"]

expected: true

case 5

in: ["mississippi","mis*is*p*."]

expected: false

case 6

in: ["","c*"]

expected: true

Starter codePython

def regex_match(s, p):
    # Your code here
    pass

6 test cases · run your code against them in the editor