10

Regular Expression

Difficulty: HARD
Contributed By
Prateek Kalyani
Avg. time to solve
25 min
Success Rate
80%

Problem Statement
Suggest Edit

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

1. ‘.’ matches to any single character.
2. ‘*’ matches to zero or more of the preceding element.

If the input string 'S' matches the pattern 'P', then return true else, return false.

Note:
1. You have to match the entire string with the pattern given.

2. Both the strings, 'S' and 'P' contain only lower-case alphabets.

3. Only the pattern will contain additional characters ‘*’ and ‘.’ along with alphabets.
Input Format:
The first line contains a single integer T representing the number of test cases.

The one and only line of each test case contains two space-separated strings 'S' and 'P' respectively. 
Output Format :
For each test case, print a single line containing “true” if the string matches the pattern, else print ”false”.

The output of every test case is printed in a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 1000
1 <= M <= 1000    

Where 'T' is the number of test cases, ‘N’ is the length of the input string to be matched, and ‘M’ is the length of the pattern 'P'.

Time limit: 1 sec.
Sample Input 1:
2
aa a
aa a*
Sample Output 1:
false
true
Explanation of Sample output 1
For the first test case, it is clearly visible that “aa” is not equal to “a”.

For the second 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.
Sample Input 2:
3
ab .*
aab c*a*b
mississippi mis*is*p*
Sample output 2:
true
true 
false 
Explanation of Sample output 2:
For the first test case, we can replace the dot with any character so “.*” means zero or more (*) of any character (.). So we can replace (*) with a (.). i.e. .* --> .. --> ab. 

For the second test case, c can be repeated zero times, a can be repeated 1 time. Therefore it matches “aab”.

For the third test case, there is no way possible to bring an ‘i’ in the end, hence the answer is false.
Reset Code
Full screen
copy-code
Console