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]))
}
}
}
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.
