Regular Expression Match
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.
Let str = “abc?" and pat= “abcd” We return true as ‘?’ can be replaced with ‘d’ and this makes ‘str’ and ‘pat’ same.
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’.
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.
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.
1 <= T <= 10 1 <= pat.length() <= 200 1 <= str.length() <= 200 Time Limit: 1sec
Try to do this problem in O(M * N).