Array String Dynamic Programming Memoization Tabulation
Guru Level

Implement the regularExpressionMatchSimple method that checks whether text matches a simplified regular expression pattern.

The input contains a string text and a pattern pattern. Your task is to check whether the pattern matches the complete string.

The pattern supports two special symbols: . matches any single character, and * means zero or more occurrences of the previous character.

For example, a* can match aa, and .* can match any string.

Example 1
Input:
text (string) = aa
pattern (string) = a*
Return:
(boolean) true
Example 2
Input:
text (string) = aa
pattern (string) = a
Return:
(boolean) false
Example 3
Input:
text (string) = ab
pattern (string) = .*
Return:
(boolean) true

Use dynamic programming because matching depends on smaller parts of the text and pattern.

Let dp[i][j] mean whether the first i characters of text match the first j characters of pattern.

When the pattern character is a normal character or ., compare it with the current text character. When the pattern character is *, handle two cases: use zero occurrences of the previous pattern character, or use one more occurrence if it matches the current text character.

Pseudocode:

function regularExpressionMatchSimple(text, pattern):
    m = length of text
    n = length of pattern
    create dp table of size (m + 1) x (n + 1) with false values
    dp[0][0] = true
    for j from 2 to n:
        if pattern[j - 1] == *:
            dp[0][j] = dp[0][j - 2]
    for i from 1 to m:
        for j from 1 to n:
            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[m][n]
Run your code to see the result.