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) =
aapattern (string) =
aReturns (boolean)
falseExample 2
Input
text (string) =
aapattern (string) =
a*Returns (boolean)
trueExample 3
Input
text (string) =
aabpattern (string) =
c*a*bReturns (boolean)
trueUse 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]Ready to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run