Regular Expression Match

Given a string ‘str’ and a string ‘pat’. The string s has some wildcard characters i.e ‘?’ and ‘*’.

If any character is a ‘?’ we can replace that character with any other character. 

If a character is a * we can replace * with any sequence of characters including the empty sequence.  

Your task is to determine if it is possible that we can make ‘str' = 'pat’ using appropriate conversions in ‘str’.

For example:

Let str = “abc?" and pat= “abcd”

We return true as ‘?’ can be replaced with ‘d’ and this makes ‘str’ and ‘pat’ same.

Input Format:

The first line of input contains an integer ‘T’ which contains the number of test cases. 

The next '2 * T' lines represent the 'T' test cases.

The first line of each test case contains the string ‘str’.

The second line of each test case contains the string ‘pat’.

Output Format:

For each test case return true if it is possible to modify string ‘str’ such that ‘pat’ is a substring of ‘s’ under given rules and conditions. Otherwise, return false.

Note:

You do not need to print anything; it has already been taken care of, Just implement the given function.

The words do not contain whitespace.

The string ‘pat’ contains only lowercase English alphabets.

Constraints:

1 <= T <= 10
1 <= pat.length() <= 200
1 <= str.length() <= 200

Time Limit: 1sec

Follow Up:

Try to do this problem in O(M * N).