String Dynamic Programming Pattern Matching
Guru Level

Implement the regularExpressionMatch method that checks full string matching with dot and star pattern rules.

You are given a text string and a pattern. The pattern may contain lowercase letters, ., and *.

The dot matches any single character. The star means zero or more occurrences of the previous pattern character. Return true only when the whole text matches the whole pattern.

Example 1
Input:
text (string) = aa
pattern (string) = a
Return:
(boolean) false
Example 2
Input:
text (string) = aa
pattern (string) = a*
Return:
(boolean) true
Example 3
Input:
text (string) = aab
pattern (string) = c*a*b
Return:
(boolean) true

Use dynamic programming on the text prefix and pattern prefix.

Let dp[i][j] mean that the first i characters of the text match the first j characters of the pattern. For a normal character or dot, the current characters must match and the previous prefixes must also match. For star, either ignore the previous pattern character with star, or use it to consume one matching text character.

This avoids recursive backtracking that can become very slow.

Pseudocode:

function regularExpressionMatch(text, pattern):
    create dp table with false
    dp[0][0] = true
    for j from 2 to pattern.length:
        if pattern[j - 1] == '*':
            dp[0][j] = dp[0][j - 2]
    for i from 1 to text.length:
        for j from 1 to pattern.length:
            if pattern[j - 1] == text[i - 1] or pattern[j - 1] == '.':
                dp[i][j] = dp[i - 1][j - 1]
            else if pattern[j - 1] == '*':
                dp[i][j] = dp[i][j - 2]
                if pattern[j - 2] == text[i - 1] or pattern[j - 2] == '.':
                    dp[i][j] = dp[i][j] or dp[i - 1][j]
    return dp[text.length][pattern.length]
Run your code to see the result.