Algorithms With JavaScript: Regular Expression Matching (Dynamic Programming)

As per usual, in this blog post we will practice solving some algorithms problems. And today our leetcode problem is: Regular Expression Matching.

Problem definition:

Given an input string (s) and a pattern (p), implement regular expression matching with support for ‘.’ and ‘*’.

‘.’ Matches any single character.

‘*’ Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

Note:

s could be empty and contains only lowercase letters a-z.

p could be empty and contains only lowercase letters a-z, and characters like . or *.

Dynamic programming

We will try to solve this problem with the help of dynamic programming. To solve this problem first we will construct a table of booleans. Size of the table depends on the length of the input string. Then we will go over the string and pattern check if pattern is matched and update values in the table.

Initial table:

Array.from({ length: s.length+1 }, () => [false])