Regular Expression Matching

The given problem is to implement regular expression matching with support for . and *. The solution can be tackled using recursion or dynamic programming. We’ll start with the recursive approach, and then we can optimize it using dynamic programming.

Here’s the code for a recursive approach:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        # Base case: If the pattern is empty, then return True if and only if the string is empty
        if not p:
            return not s

        # Check if the first character matches (either the same character or '.')
        first_match = bool(s) and p[0] in {s[0], '.'}

        # If the pattern has a '*', we have two possibilities:
        # 1. Ignore '*' and the preceding character, i.e., p[2:].
        # 2. Use '*' to match the current character in s and move to the next character, i.e., s[1:].
        if len(p) >= 2 and p[1] == '*':
            return (self.isMatch(s, p[2:])) or (first_match and self.isMatch(s[1:], p))
        else:
            return first_match and self.isMatch(s[1:], p[1:])

The recursion deals with two base cases:

If p is empty, s must also be empty for a match.
If p has a * at the next position, we can either ignore it or use it to match one character in s.

The recursive approach, while simple and clear, leads to duplicated work. This can be avoided with dynamic programming (DP). Here’s a top-down DP approach:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        memo = {}

        def dp(i: int, j: int) -> bool:
            if (i, j) not in memo:
                if j == len(p):
                    ans = i == len(s)
                else:
                    first_match = i < len(s) and p[j] in {s[i], '.'}
                    if j + 1 < len(p) and p[j+1] == '*':
                        ans = dp(i, j+2) or (first_match and dp(i+1, j))
                    else:
                        ans = first_match and dp(i+1, j+1)

                memo[i, j] = ans

            return memo[i, j]

        return dp(0, 0)

The dp function checks for matches starting at positions i and j in s and p, respectively. By storing previously computed results in memo, we avoid redundant work, greatly improving efficiency.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        i, j = len(s) - 1, len(p) - 1
        return self.backtrack({}, s, p, i, j)

    def backtrack(self, cache, s, p, i, j):
        key = (i, j)
        if key in cache:
            return cache[key]

        if i == -1 and j == -1:
            cache[key] = True
            return True

        if i != -1 and j == -1:
            cache[key] = False
            return cache[key]

        if i == -1 and p[j] == '*':
            k = j
            while k != -1 and p[k] == '*':
                k -= 2

            if k == -1:
                cache[key] = True
                return cache[key]

            cache[key] = False
            return cache[key]

        if i == -1 and p[j] != '*':
            cache[key] = False
            return cache[key]

        if p[j] == '*':
            if self.backtrack(cache, s, p, i, j - 2):
                cache[key] = True
                return cache[key]

            if p[j - 1] == s[i] or p[j - 1] == '.':
                if self.backtrack(cache, s, p, i - 1, j):
                    cache[key] = True
                    return cache[key]

        if p[j] == '.' or s[i] == p[j]:
            if self.backtrack(cache, s, p, i - 1, j - 1):
                cache[key] = True
                return cache[key]

        cache[key] = False
        return cache[key]

Problem Classification

This problem can be classified as a Pattern Matching problem.

This is because the problem deals with two strings - a text and a pattern, and the task is to determine if the pattern matches the text considering special characters in pattern like ‘.’ and ‘*’. So, the primary focus of the problem is recognizing and matching patterns, thus fitting into the Pattern Matching category.

Language Agnostic Coding Drills

Variables: Understanding variable declaration, assignment, and usage.
Data Structures: Understanding how to use lists and tuples.
Control Structures: Understanding if-else conditions and loop constructs.
Functions: Understanding function definition, parameters, and calling.
Classes: Understanding class creation, object instantiation, and method definition.
Recursion: Understanding the concept of recursion where a function calls itself.
Memoization/Caching: Understand how to use a dictionary to store pre-computed values to avoid duplicate computation (dynamic programming).
Backtracking: The method used in this code to traverse through all the possibilities until a solution is found.

To arrive at the final solution from the problem statement:

Understand the problem statement: Recognize that this is a pattern matching problem that can be solved using dynamic programming and recursion.
Formulate the approach: Map out the backtracking approach where each character of the given string is checked against the pattern.
Implement the approach: Code the class and method structures, implement the backtracking logic using recursion, use a cache to store pre-computed results.
Test and debug: Run the code with multiple test cases to ensure it’s working as expected, debug any errors.

Targeted Drills in Python

Variables
Drill: Write a Python program that declares several variables, assigns values to them and prints them.

1
2
3
4
5
6
# declaring and assigning value to variables
a = 5
b = 10

# print the variables
print(f'a: {a}, b: {b}')

Data Structures
Drill: Create a Python list and tuple, perform various operations (add, remove, access elements) on them.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
# creating a list and tuple
my_list = [1, 2, 3]
my_tuple = (1, 2, 3)

# adding elements to list
my_list.append(4)

# accessing elements
print(my_list[1])  # 2
print(my_tuple[2])  # 3

Control Structures
Drill: Write a Python program that uses if-else conditions and loop constructs.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
# declaring a variable
n = 5

# if-else construct
if n > 0:
    print("n is positive")
else:
    print("n is non-positive")

# loop construct
for i in range(n):
    print(i)

Functions
Drill: Write a Python function that takes two parameters and returns their sum.

1
2
3
4
def add(a, b):
    return a + b

print(add(3, 4))  # 7

Classes
Drill: Write a Python class that has a constructor, one instance variable, and one instance method.

1
2
3
4
5
6
7
8
9
class MyClass:
    def __init__(self, value):
        self.value = value

    def display_value(self):
        print(self.value)

obj = MyClass(10)
obj.display_value()  # 10

Recursion
Drill: Write a recursive Python function that computes the factorial of a number.

1
2
3
4
5
6
7
def factorial(n):
    if n == 0 or n == 1:
        return 1
    else:
        return n * factorial(n - 1)

print(factorial(5))  # 120

Memoization/Caching
Drill: Implement a Python function that calculates the nth Fibonacci number using dynamic programming.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def fibonacci(n, cache={}):
    if n in cache:
        return cache[n]
    elif n <= 2:
        cache[n] = 1
    else:
        cache[n] = fibonacci(n-1) + fibonacci(n-2)
    return cache[n]

print(fibonacci(10))  # 55

Backtracking
Drill: Implement a Python function that generates all possible permutations of a given list of elements using backtracking.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def permute(nums, index=0):
    if index == len(nums) - 1:
        print(nums)
    else:
        for i in range(index, len(nums)):
            nums[index], nums[i] = nums[i], nums[index]
            permute(nums, index + 1)
            nums[index], nums[i] = nums[i], nums[index]

permute([1, 2, 3])

These drills should give you a good understanding of the basic constructs used in the problem code.