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:


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.




Upskilling students for tech placements!

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Scientific Troubleshooting Framework

PHP debugging on Ubuntu

Transparent editing of GPG encrypted files with Vim

How to use Visual Studio Code

Real-Time Marketing Data Analysis Based on Hologres + Flink

AWS Integration & Messaging: SQS, SNS & Kinesis

Effective Retrospectives — Key to high performing teams!

EDIUS: export from Simon Says and import directly into EDIUS

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store


Upskilling students for tech placements!

More from Medium

Monkey Door Puzzle

Oracle Interview Experience (On-Campus)

LeetCode 146. LRU Cache

Interview Preparation Series