DP #38. Regex Matching. - mbhushan/dynpro GitHub Wiki
(38). Regular Expression Matching.
Implement regular expression matching with support for ‘.’ and ‘*’.
‘.’ Matches any single character.
‘*’ Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch(“aa”,”a”) → false
isMatch(“aa”,”aa”) → true
isMatch(“aaa”,”aa”) → false
isMatch(“aa”, “a*”) → true
isMatch(“aa”, “.*”) → true
isMatch(“ab”, “.*”) → true
isMatch(“aab”, “c*a*b”) → true
Formula:
i <- String indices
j <- pattern indices
//Deals with patterns like a* or a*b* or a*b*c*
for (int i = 1; i < T[0].length; i++) {
if (P.charAt(i-1) == '*') {
T[0][i] = T[0][i - 2];
}
}
If (S[i] == P[j] || P[j] == '.') {
T[i][j] = T[i-1][j-1]
} else if (P[j] == '*') {
T[i][j] = T[i][j-2] // zero occurances.
If (S[i] == P[j-1] || P[j-1] == '.') {
T[i][j] = T[i-1][j]
}
} else {
T[i][j] = false;
}
Time Complexity: O(n*m)
Space Complexity: O(n*m)
| (str, pat) | 0 | x | a | * | b | . | c |
| 0 | T | F | F | F | F | F | F |
| x | F | T | F | T | F | F | F |
| a | F | F | T | T | F | F | F |
| a | F | F | F | T | F | F | F |
| b | F | F | F | F | T | F | F |
| y | F | F | F | F | F | T | F |
| c | F | F | F | F | F | F | T (match) |