10. Regular Expression Matching - Detailed Explanation

Problem Statement

Description:
Given an input string s and a pattern p, implement regular expression matching with support for the special characters . and *. The matching must cover the entire string (not just a substring). The rules are:

• . (dot) matches any single character. For example, "a" matches "." because . can represent "a" (or any other single char).
• * (star) matches zero or more of the preceding character. It means the character immediately before * can repeat any number of times (including 0 times). For example, "bo*" can match "b", "bo", "boo", "booo", etc., because * allows 'o' to appear 0 or more times.

The goal is to return a boolean indicating whether s matches p exactly according to these rules.

Examples:

1. Input: s = "aa", p = "a" – Output: false.
   Explanation: The pattern "a" is a single character and cannot match the two-character string "aa" (it would only match a single "a").

2. Input: s = "aa", p = "a*" – Output: true.
   Explanation: '*' means "zero or more of the preceding element". Here the preceding element is 'a'. So "a*" can represent "" (zero a's), "a", "aa", "aaa", etc. By repeating 'a' once, "a*" becomes "aa", which matches the string.

3. Input: s = "ab", p = ".*" – Output: true.
   Explanation: ".*" means "zero or more of .". The . can match any single character, and * allows any number of that. So ".*" can match any string, including "ab" (here, ".*" can expand to two characters, matching "ab").

4. Input: s = "aab", p = "c*a*b" – Output: true.
   Explanation: The pattern can be read as "c*" followed by "a*" followed by "b". "c*" can match zero 'c' characters (since the string doesn’t have c), "a*" can match "aa" (two 'a' characters), and then "b" matches "b". All characters in s are matched by the pattern in order, so it returns true.

5. Input: s = "mississippi", p = "mis*is*p*." – Output: false.
   Explanation: The pattern "mis*is*p*." is trying to match "mississippi", but it fails. For instance, "mis*" can match "mis" (the s* part can match "s"), and "is*" can match "iss" or "is", etc. Ultimately, no matter how the * wildcards are expanded, the pattern cannot fully cover "mississippi" correctly, so the result is false.

Constraints:

• 1 <= s.length <= 20

• 1 <= p.length <= 20

• s contains only lowercase English letters.

• p contains only lowercase English letters, '.', and '*'.

• The pattern p is guaranteed to be well-formed, meaning every '*' has a valid preceding character (no standalone * at the start or double ** in pattern).

Hints

• Think Recursively: Try to break the matching problem into smaller subproblems. Consider matching the first character of the string and pattern and then recursively solving the rest. How would . or * affect this process? For example, if the pattern’s second character is *, you have two options: use the * (consume a character of s if it matches the preceding pattern char) or skip the * (treat the preceding char as repeating zero times). This hint suggests a branching (backtracking) approach for handling *.

• Simple Case First: If there were no * in the pattern, the problem would be simpler – you’d just check each character (with . matching anything) and ensure the lengths match. Use this as a sub-solution. Once you handle direct character matches and ., incorporate the * logic.

• Dynamic Programming: Consider using DP to store results of subproblems (e.g., whether s[i:] matches p[j:]). There are overlapping subproblems in the recursive solution (the same substring and subpattern might be evaluated multiple times), so caching those results can help. Think of a DP table dp[i][j] meaning: Does the substring s[0..i-1] match the subpattern p[0..j-1]? If you can derive a recurrence for dp[i][j] based on smaller indices, you’re on the right track.

• Base Cases: What happens when the string is empty or the pattern is empty? An empty pattern only matches an empty string. A pattern like "x*" can match an empty string because x* can repeat x zero times. These cases are important to handle explicitly.

Multiple Approaches

There are several ways to solve this problem. We’ll discuss a brute-force backtracking approach and then an optimized dynamic programming approach. The brute-force solution is conceptually simpler but inefficient for larger inputs, while the DP solution is optimal for this problem.

Brute-Force Approach (Recursion & Backtracking)

Idea: Try all possibilities using recursion. We attempt to match the string and pattern from the start, character by character, handling . and * with special rules. Whenever we encounter a * in the pattern, we branch out into two possibilities :

1. Use the *: If the preceding character of the pattern matches the current character of the string (or is . which matches anything), consume one character from the string and stay on the same pattern index (since * can represent more of that character). This allows the * to cover one more character of the string.
2. Skip the *: Ignore the "<char>*" in the pattern (treat it as matching zero occurrences of that char). This means we move past the * in the pattern (effectively deleting that part of the pattern), without consuming any character from the string.

We recursively try both options if applicable. If at any point characters don’t match (and the pattern char isn’t . or the pattern is exhausted while string remains), that path is a dead end (returns false). If we reach the end of both string and pattern simultaneously, we have a match (return true).

Why it’s inefficient: In the worst case, the branching can explode exponentially. For example, a pattern like "a*a*a*..." and a string of all 'a' can cause many recursive calls by either skipping or using each * in different ways. Without any optimization, the same subproblems get solved repeatedly. For instance, you might recompute whether "issippi" matches "s*p*." many times in a naive recursion. This redundant work leads to an exponential time complexity in the worst case. A pure backtracking solution may time out for larger strings. (It can pass within the given constraints since lengths are ≤ 20, but it’s not efficient or reliable for bigger inputs.) In summary, the brute-force approach explores a huge decision tree of matches and has exponential time complexity, so we need to optimize.

Optimal Dynamic Programming Approach (Bottom-Up)

Idea: Use dynamic programming to avoid recomputation of subproblems. We create a DP table where dp[i][j] is a boolean indicating whether the first i characters of s (i.e. s[0..i-1]) can be matched by the first j characters of p (p[0..j-1]). The final answer will be dp[n][m] where n = len(s) and m = len(p). We fill this table iteratively using the rules of matching. Dynamic programming works here because the problem exhibits optimal substructure (a solution can be built from solutions of subproblems) and overlapping subproblems (the same substrings get checked multiple times in brute force).

DP Table Setup:

• We use dimensions (n+1) x (m+1) because we include the case of the empty string and empty pattern (index 0 represents "no characters"). dp[0][0] (empty string vs empty pattern) is true – that's our base case.

• The first row dp[0][j] (empty string vs some pattern) needs initialization. An empty string can only match a pattern that is capable of representing an empty sequence. This would be patterns like "a*" or "x*y*z*", etc., where each * can eliminate the preceding character. Specifically, for dp[0][j] (with j > 0), dp[0][j] is true if and only if the pattern up to j ends in a * that can represent zero occurrences. In practice, we can initialize: for any pattern like p[0..j-1] that is something like "A*B*C*..." (even length, every second char is *), dp[0][j] = true. Typically, we set dp[0][j] = dp[0][j-2] if p[j-1] == '*' (meaning we drop that char* pair). For example, if p = "c*" then dp[0][2] should be true because c* can match an empty string by taking 0 occurrences of 'c'.

• The first column dp[i][0] (non-empty string vs empty pattern) will be all false for i > 0 because a non-empty string cannot match an empty pattern.

Transition Rules: We fill the table row by row (or recursively compute states) using these rules for each position (i, j):

1. Direct Character Match or .: If the current pattern character p[j-1] is a letter or . (not *), then it matches the current string character s[i-1] if and only if either they are the same letter or the pattern char is .. In that case, the result for dp[i][j] depends on the previous state dp[i-1][j-1] (the prefixes without these characters). In formula:

   if p[j-1] == s[i-1] or p[j-1] == '.':
       dp[i][j] = dp[i-1][j-1]
   

   This means if the current characters match, we have a match up to i,j if and only if the prefixes up to i-1,j-1 matched.

2. * Wildcard: If the current pattern character is * (at p[j-1]), then we have to consider it as representing two scenarios:

   • Zero occurrences of the preceding character: We can "drop" the <char>* pair from the pattern. This means we look two pattern characters back and see if that matches the current i characters of string: dp[i][j] = dp[i][j-2] (we ignore the x* and see if dp[i][j-2] was true). For example, if pattern is "b*" and we want to see if it matches "abc" up to some point, the b* could match nothing and we rely on whatever was before it.

   • One or more occurrences of the preceding character: The * can match at least one occurrence of the char before it. This requires that the preceding pattern character p[j-2] matches the current string character s[i-1] (or is .), and if so, we can consume that character from s and still have the pattern j stay at the same position (because * can handle more of this char). In terms of DP, if p[j-2] matches s[i-1], then we look at dp[i-1][j] . dp[i-1][j] represents that the string up to i-1 can be matched by the pattern up to this *. If that was true, and the current char matches, then dp[i][j] can also be true by extending that match with this one character. In formula:

   if p[j-1] == '*':
       dp[i][j] = dp[i][j-2]   // treat x* as empty
                 or ( (p[j-2] == s[i-1] or p[j-2] == '.') 
                      and dp[i-1][j] )
   

   This encapsulates the two possibilities: ignore the x* or use it to match this character of s (and maybe more).

By filling out the table with these rules, we eventually compute the answer. The dynamic programming ensures each subproblem (combination of i and j) is solved once, giving an overall polynomial time solution.

Step-by-Step Walkthrough of DP Solution

To illustrate the DP approach, let’s walk through a concrete example and build the DP table.

We’ll work through the example where:

• s = "aab"
• p = "cab"

Our goal is to fill a DP table where:

• dp[i][j] is true if the first i characters of s (i.e. s[0..i‑1]) match the first j characters of p (i.e. p[0..j‑1]).
• We create a table with dimensions (n+1) x (m+1), where n = len(s) = 3 and m = len(p) = 5.
• The extra row and column (index 0) represent the empty string/pattern.

Step 1. Table Layout

We label the rows and columns as follows:

• Rows (i):

  • i = 0: Empty string ""
  • i = 1: "a"
  • i = 2: "aa"
  • i = 3: "aab"

• Columns (j):

  • j = 0: Empty pattern ""
  • j = 1: Pattern "c"
  • j = 2: Pattern "c*"
  • j = 3: Pattern "c*a"
  • j = 4: Pattern "c*a*"
  • j = 5: Pattern "c*a*b"

Step 2. Base Case Initialization

1. dp[0][0] = True
   (Empty string matches empty pattern.)

2. First Row (i = 0): Matching Empty String with Pattern
   We must decide whether an empty string can match a non-empty pattern. Only patterns that can “disappear” (via *) may match an empty string.

   • dp[0][1]: Pattern = "c"
     • "c" cannot match empty. dp[0][1] = False.
   • dp[0][2]: Pattern = "c*"
     • Here, * means zero or more 'c'. Taking zero occurrences, "c*" becomes empty.
       dp[0][2] = dp[0][0] = True.
   • dp[0][3]: Pattern = "c*a"
     • Although "c*" can vanish, the trailing "a" must match something. dp[0][3] = False.
   • dp[0][4]: Pattern = "c*a*"
     • Now both "c*" and "a*" can vanish.
       dp[0][4] = dp[0][2] = True.
   • dp[0][5]: Pattern = "c*a*b"
     • The ending "b" cannot vanish. dp[0][5] = False.

After initialization, the first row (i = 0) is:

dp[0] = [T, F, T, F, T, F]

Step 3. Fill the Table Row by Row

Now, we fill in the rest of the table using the recurrence rules.
Recall the rules:

• For a direct match or a dot (.):
  If p[j‑1] equals s[i‑1] or is ., then:
  dp[i][j] = dp[i‑1][j‑1]

• For a star (*):
  Let the star be at p[j‑1] and its preceding character be p[j‑2]. Then:

  dp[i][j] = dp[i][j‑2]    // Treat "x*" as matching zero occurrences
             OR
             (if (p[j‑2] == s[i‑1] or p[j‑2] == '.') then dp[i‑1][j])
             // Use "x*" to match one or more occurrence
  

Row i = 1 (s = "a")

s[0] = 'a'

• dp[1][0]:
  Non-empty string vs. empty pattern → False.

• dp[1][1]: Pattern "c" vs. "a"

  • 'c' does not match 'a' → False.

• dp[1][2]: Pattern "c*" vs. "a"

  • Two choices:
    • Skip "c*": dp[1][0] = False.
    • Use "c*": Check if 'c' matches 'a' (it does not).
  • So, dp[1][2] = False.

• dp[1][3]: Pattern "c*a" vs. "a"

  • Last char in pattern is 'a' which matches 'a'.
  • dp[1][3] = dp[0][2] (what was the result for empty string vs. "c*"?)
  • From above, dp[0][2] = True.
  • Thus, dp[1][3] = True.

• dp[1][4]: Pattern "c*a*" vs. "a"

  • Here p[3] is '*'. Two cases:
    • Skip "a*": dp[1][4] = dp[1][2] = False.
    • Use "a*": Check if preceding char 'a' (p[2]) matches 'a' (s[0]). It does.
      Then, dp[1][4] = dp[0][4].
      From the first row, dp[0][4] = True.
  • So, dp[1][4] = True.

• dp[1][5]: Pattern "c*a*b" vs. "a"

  • Last char in pattern is 'b' but s[0] is 'a'.
  • dp[1][5] = False.

Now row i = 1 becomes:

dp[1] = [F, F, F, T, T, F]

Row i = 2 (s = "aa")

s = "aa", s[1] = 'a'

• dp[2][0]: → False.

• dp[2][1]: Pattern "c" vs. "aa"

  • 'c' does not match 'a' → False.

• dp[2][2]: Pattern "c*" vs. "aa"

  • Choices:
    • Skip "c*": dp[2][0] = False.
    • Use "c*": Check if 'c' matches s[1] = 'a' → No.
  • So, dp[2][2] = False.

• dp[2][3]: Pattern "c*a" vs. "aa"

  • Last char 'a' should match s[1] = 'a'.
  • Then, dp[2][3] = dp[1][2] (check the match for "a" vs. pattern "c*").
  • From row i = 1, dp[1][2] = False.
  • So, dp[2][3] = False.

• dp[2][4]: Pattern "c*a*" vs. "aa"

  • p[3] is '*' → two cases:
    • Skip "a*": dp[2][4] = dp[2][2] = False.
    • Use "a*": Check if preceding char 'a' (p[2]) matches s[1] = 'a' → Yes.
      Then, dp[2][4] = dp[1][4].
      From row i = 1, dp[1][4] = True.
  • Thus, dp[2][4] = True.

• dp[2][5]: Pattern "c*a*b" vs. "aa"

  • Last char in pattern is 'b', which does not match s[1] = 'a'.
  • So, dp[2][5] = False.

Now row i = 2 becomes:

dp[2] = [F, F, F, F, T, F]

Row i = 3 (s = "aab")

s = "aab", s[2] = 'b'

• dp[3][0]: → False.

• dp[3][1]: Pattern "c" vs. "aab"

  • 'c' does not match 'b' → False.

• dp[3][2]: Pattern "c*" vs. "aab"

  • Two cases:
    • Skip "c*": dp[3][2] = dp[3][0] = False.
    • Use "c*": Check if 'c' matches s[2] = 'b' → No.
  • So, dp[3][2] = False.

• dp[3][3]: Pattern "c*a" vs. "aab"

  • Last char in pattern is 'a', but s[2] is 'b' → False.

• dp[3][4]: Pattern "c*a*" vs. "aab"

  • p[3] is '*'.
    • Skip "a*": dp[3][4] = dp[3][2] = False.
    • Use "a*": Check if preceding char 'a' (p[2]) matches s[2] = 'b' → No.
  • So, dp[3][4] = False.

• dp[3][5]: Pattern "c*a*b" vs. "aab"

  • Last char 'b' in pattern should match s[2] = 'b' → It does.
  • Then, dp[3][5] = dp[2][4] (we check if "aa" matches "c*a*").
  • From row i = 2, dp[2][4] = True.
  • So, dp[3][5] = True.

Now row i = 3 becomes:

dp[3] = [F, F, F, F, F, T]

Step 4. Final DP Table

Putting it all together, the complete DP table is:

The final answer is given by dp[3][5], which is True. This means that the string "aab" matches the pattern "c*a*b".

Summary

• We started by initializing dp[0][0] as true and filling out the first row using the rule for *.
• Then, we filled each row using two rules: one for direct character (or dot) matches and one for handling *.
• The final result dp[3][5] = True confirms that "aab" matches "c*a*b".

This step-by-step walkthrough shows how the DP table is built and used to solve the Regular Expression Matching problem.

Python Solution