Regular expression — Asked in Google, Flipkart and Facebook Interview
Problem Statement :
Given an input string ‘S’ and a pattern ‘P’, implement a regular expression matching with the support of two special characters ‘.’ (dot) and ‘*’(asterisk) where :
‘.’ matches to any single character.
‘*’ matches to zero or more of the preceding element.
S = aa, P = a*
Explanation of Test Case :
‘*’ means that we can replace zero or more of the preceding element. Hence we can replace it with another ‘a’. So, the given string can be formed with the pattern.
Time Complexity — O(N*M)
Space Complexity — O(N*M)