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
aaa*trueExample 2
aaafalseExample 3
ab.*trueUse 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]