 New update is available. Click here to update.

# Regular Expression Matching

Posted: 23 Jan, 2021
Difficulty: Hard

## 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

``````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.
``````
SIMILAR PROBLEMS

DECODE STRING

Posted: 11 Sep, 2022
Difficulty: Moderate

Cakes

Posted: 23 Sep, 2022
Difficulty: Easy

1-3 Palindrome

Posted: 4 Oct, 2022
Difficulty: Easy

Randomly Sorted

Posted: 13 Nov, 2022
Difficulty: Moderate

8-Queen Problem

Posted: 19 Dec, 2022
Difficulty: Easy