NUHMAN.com

Introduction

LeetCode 10: Regular Expression Matching is a classic dynamic programming challenge that tests your understanding of pattern matching. The goal is to implement a basic regex engine supporting two special characters:

• . – matches any single character
• * – matches zero or more of the preceding element

In this article, we’ll explore an efficient dynamic programming solution using Go, and break it down in a clear and understandable way.

Problem Statement

Given a string s and a pattern p, implement regular expression matching with support for . and *.

Return true if the input string s matches the pattern p, otherwise return false.

Examples

go

Input: s = "aa", p = "a"
Output: false
go

Input: s = "aa", p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding 'a'
go

Input: s = "ab", p = ".*"
Output: true

Clarifying the Rules

• . matches any single character.
• * means zero or more of the character immediately before it.

Important: The match must cover the entire string.

Approach: Dynamic Programming (Bottom-Up)

We define a 2D DP table dp[i][j]:

• dp[i][j] = true means s[0:i] matches p[0:j]

Initialization:

• dp[0][0] = true — empty string matches empty pattern.
• Handle patterns like a*, a*b* that can match an empty string.

Transition:

• If p[j-1] == s[i-1] || p[j-1] == '.' → dp[i][j] = dp[i-1][j-1]
• If p[j-1] == '*':
• Match zero of the preceding: dp[i][j] = dp[i][j-2]
• Match one or more if s[i-1] == p[j-2] || p[j-2] == '.': dp[i][j] |= dp[i-1][j]

Go Implementation

go

package main

import (
    "fmt"
)

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

    dp[0][0] = true

    // Initialize for patterns like a*, a*b*, a*b*c*
    for j := 2; j <= n; j++ {
        if p[j-1] == '*' {
            dp[0][j] = dp[0][j-2]
        }
    }

    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] // Zero occurrence
                if p[j-2] == s[i-1] || p[j-2] == '.' {
                    dp[i][j] = dp[i][j] || dp[i-1][j] // One or more
                }
            }
        }
    }

    return dp[m][n]
}

func main() {
    tests := []struct {
        s string
        p string
    }{
        {"aa", "a"},
        {"aa", "a*"},
        {"ab", ".*"},
        {"mississippi", "mis*is*p*."},
        {"mississippi", "mis*is*ip*."},
    }

    for _, t := range tests {
        fmt.Printf("isMatch(%q, %q) = %v\n", t.s, t.p, isMatch(t.s, t.p))
    }
}

How It Works

For s = "aab" and p = "c*a*b":

• c* matches 0 cs
• a* matches two as
• b matches b
• → Match found.

Time and Space Complexity

• Time Complexity: O(m × n)
• Space Complexity: O(m × n)

Key Takeaways

• This is not a simple regex engine — it needs full string matching.
• Use a DP table to handle overlapping subproblems.
• The two cases for * are crucial: match zero or many.