Problem

Submissions

Solution

New

Discuss

10

Avg. time to solve

25 min

Success Rate

80%

Problem Statement

Suggest Edit

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

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

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

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

```
You do not need to print anything. It has already been taken care of. Just implement the given function.
```

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

```
2
aa a
aa a*
```

```
false
true
```

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

```
3
ab .*
aab c*a*b
mississippi mis*is*p*
```

```
true
true
false
```

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

Console