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.

Sample Input:

S = aa, P = a*

Sample Output:

true

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.

Approach :

Bottom-up DP

Time Complexity — O(N*M)
Space Complexity — O(N*M)

Code :

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.