Regular Expression Match

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

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.

For the first test case, "a" does not match the entire string "aa". For the second test case: As specified, '*' matches any sequence. Hence * is equivalent to sequence Aa and the pattern matches. So we return True. For the third test case: As specified, '?' matches with any single character. So we match ‘?’ with 'c', but the second letter is 'a', which does not match with 'b'. So we return false For the fourth test case: As specified, '*' matches any sequence. Hence,the first '*' matches the empty sequence, while the second '*' matches the substring "dce". So we return true

Recursion Based Approach

The idea is pretty straightforward: scan ‘str’ and ‘pat’ while there is a match between the current character of ‘str’ and the current character of ‘pat’. If we reach the end of both strings while there is still a match, return True, otherwise, return False. The scan is done by having a pointer ‘i’ in ‘str’ and a pointer ‘j’ in ‘pat'

Example: = "code"

The character 'c' of 'str matches the first character of ‘pat’ if the first character of ‘pat’ is:

'c' OR '?' OR '*'

When the first character of ‘pat’ is a lowercase letter different from 'c', return False.

If the first character of ‘pat’ is 'c' or '?', we move both pointers one step to the right.

If the first character of ‘pat’ is '*', we have 2 possibilities:

'*' matches 0 characters: in this case, we move the pointer in P one step

'*' matches 1 or more characters: in this case, we move the pointer in 'str one step

And we continue like this for every two positions taken by the two pointers.

We will have the following tree: the first number represents ‘i’ and the second number represents ‘j’

If we reach the end of ‘pat’ but there are still characters from 'str, simply return, False!

If we reach the end of ‘str’ and there are still characters from 'pat', the only case when there is a match is that all the remaining characters in 'pat' are '*', in this case, these stars will be matched with the empty string.

We can take the following approach:

Call a function helper which takes 4 variables the string ‘str’ the string ‘pat’ and 2 integer values ‘i’ and ‘j’ to keep track of the index of ‘str’ and ‘pat respectively
If the I reaches the end of the string i.e. i = str.length(), then only when pat[j] = ' * ' since * can be equal to the empty sequence as well.
We will now check if the current character of the pattern and string are equal or not. They would be equal if either str[i] == pat[j] or pat[j] = '?'.
if the current pattern character is ' * ' then we have two options either to move j forward and don't use it for matching or we can match and move the string index and keep the pattern index at j only.
if the current character is not ' * ', then we need to check only if the first_match is true and move both i and j index by 1.
Once we hit the base case, we return the answer.

Time Complexity

O(2 ^ max(M, N)), where ‘M’ is the size of ‘str’ and ‘N’ is the size of ‘pat’.

In the worst case, if we have ‘*’ at alternating places, we will recursively call the function 2 ^ max(M, N) times

Space Complexity

O(max(M, N)), where ‘M’ is the size of ‘str’ and ‘N’ is the size of ‘pat’.

Recursive stack takes space of order of max(M, N)

Problem statement

Sample Input 1:

Sample Output 1:

Explanation For Sample Input 1:

Sample Input 2:

Sample Output 2: