Regular Expression Matching Solution for Accenture

Company: Accenture · Difficulty: Easy · Topics: String, Dynamic Programming, Recursion

Problem Statement

Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where:

• '.' Matches any single character
• '*' Matches zero or more of the preceding element

Examples

Example 1:

Input: s = "aa", p = "a"

Output: false

Explanation: "a" does not match the entire string "aa".

Example 2:

Input: s = "aa", p = "a*"

Output: true

Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Example 3:

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

Output: true

Explanation: ".*" means "zero or more (*) of any character (.)".

Intuition

The key insight is that this is a dynamic programming problem where we need to match the string against the pattern character by character, handling the special cases of '.' and '*' recursively.

Approach

Approach 1: Dynamic Programming (Optimal)

1. Create a 2D DP table

2. Base cases: empty string and empty pattern

3. Handle '.' and '*' cases separately

4. Fill the DP table bottom-up

Approach 2: Recursion with Memoization

1. Use recursive function with memoization

2. Handle base cases first

3. Check for '*' and '.' patterns

4. Memoize results to avoid recalculation

Approach 3: Backtracking

1. Use backtracking approach

2. Try different combinations of '*' matches

3. Return true if any combination works

Dry Run

Let's trace through Example 2: s = "aa", p = "a*"

DP Approach:

• Create DP table: dp[3][3] (for "aa" and "a*")
• dp[0][0] = true (empty matches empty)
• dp[0][1] = false (empty doesn't match "a")
• dp[0][2] = true (empty matches "a*" with 0 repetitions)
• dp[1][0] = false (non-empty doesn't match empty)
• dp[1][1] = true (first 'a' matches first 'a')
• dp[1][2] = true (first 'a' matches "a*")
• dp[2][0] = false
• dp[2][1] = false (second 'a' doesn't match single 'a')
• dp[2][2] = true (second 'a' matches "a*")
• Final result: dp[2][2] = true

Solution

⚠️ Disclaimer: Don't jump directly to the solution, try it out yourself first. Only look at the solution after you've given it a good attempt.

Solution 1: Dynamic Programming (Optimal)

Time Complexity: O(m*n) - Fill DP table

Space Complexity: O(m*n) - DP table space

Solution 2: Recursion with Memoization

Time Complexity: O(m*n) - With memoization

Space Complexity: O(m*n) - Recursion stack + memoization

Solution 3: Backtracking

Time Complexity: O((m+n)*2^(m+n)) - Exponential

Space Complexity: O(m+n) - Recursion stack

More Accenture coding questions