Regular Expression Match Problem Statement

Given a string str and a string pat, where str may contain wildcard characters '?' and '*'.

If a character is '?', it can be replaced with any single character. If a character is '*', it can be replaced with any sequence of characters (including an empty sequence).

Your task is to determine whether it is possible to transform str such that it matches pat using the given wildcard rules.

Input:

The first line of input contains an integer T, representing 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:

For each test case, return true if it is possible to modify str such that it matches pat under the given rules; otherwise, return false.

Example:

Input:

str = "abc?", pat = "abcd"

Output:

true

Explanation:

The '?' can be replaced with 'd', making str and pat identical.

Constraints:

• 1 <= T <= 10
• 1 <= pat.length() <= 200
• 1 <= str.length() <= 200
• Time Limit: 1 sec

Note:

You do not need to print anything; just implement the function. The strings do not contain whitespace. The string pat contains only lowercase English alphabets.

Follow Up:

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