Mastering Regex Matching in Golang with Dynamic Programming

Want to learn how to solve Leetcode problem 10: Regular Expression Matching, using GoLang? Then follow along as I explain how to implement regex matching in Golang.

What is Dynamic Programming (DP)?

Dynamic programming is a problem-solving approach used to solve complex problems by breaking them down into smaller, more manageable subproblems. It is a method that solves each subproblem only once and stores the results, avoiding redundant computations and leading to more efficient solutions.

In other words, if the problem can be divided into smaller subproblems that have similar solutions, and the solution to the larger problem can be derived from the solutions to the subproblems, dynamic programming is a great approach.

For example, imagine you’re planning a trip from city A to city B, and you want to find the shortest route. You can break down the problem into smaller subproblems, such as finding the shortest route from city A to city C, and then from city C to city B. By solving each subproblem only once and storing the results, you can avoid re-computing the same information multiple times, making your solution more efficient.

Modelling the Problem

We assume that:

s: Input string.
p: Pattern containing '.' and '*'.
'.': Matches any single character.
'*': Matches zero or more of the preceding element.

Our goal is to determine if the entire string s matches the pattern p.

Solution Approach

Dynamic Programming Table

    m, n := len(s), len(p)
    dp := make([][]bool, m+1)
    for i := range dp {
        dp[i] = make([]bool, n+1)
    }

Create a 2D DP table dp where dp[i][j] is true if s[0:i] matches p[0:j].

Initialization

    dp[0][0] = true
    for j := 1; j <= n; j++ {
        if p[j-1] == '*' {
            dp[0][j] = dp[0][j-2]
        }
    }

dp[0][0] is true because an empty string matches an empty pattern.
Populate dp[0][j] for patterns like a*, ab, etc., which can match an empty string.

Filling the DP Table

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if p[j-1] == '.' || p[j-1] == s[i-1] {
                dp[i][j] = dp[i-1][j-1]
            } else if p[j-1] == '*' {
                dp[i][j] = dp[i][j-2] || (dp[i-1][j] && (p[j-2] == '.' || p[j-2] == s[i-1]))
            }
        }
    }

For each character in s and p, update the DP table based on:
- If characters match or pattern has '.', then check the previous state dp[i-1][j-1].
- If pattern has '*', then consider zero occurrence dp[i][j-2] or one/more occurrences dp[i-1][j].

Code Explanation

DP Table Initialization

We initialize a DP table dp with dimensions (m+1) x (n+1) where m is the length of s and n is the length of p.

Base Case

dp[0][0] = true: An empty string matches an empty pattern.
Handle patterns like a*, ab, etc., that can match an empty string.

Filling the Table

Loop through each character of s and p to fill dp[i][j]:
If characters match or pattern has '.', set dp[i][j] = dp[i-1][j-1].
If pattern has '*', check for zero occurrence dp[i][j-2] or one/more occurrences dp[i-1][j].

Conclusion

And that's it! Leveraging Dynamic Programming, we were able to solve this problem in a concise manner.

PhantomExclusive