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

Question

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

Accepted Answer

I first asked him to give me 2 minutes to think about the approach. In those 2 minutes I decided how am I going to explain him my logic and how to start coding. Then I explained him my logic and started coding. While coding I used to think loud and told him why I am using loop or particular variable.

Accepted Answer

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.

Space Complexity: O(1)Explanation:

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)

Time Complexity: OtherExplanation:

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

Accepted Answer

Dynamic Programming

The key idea is that from the recursion tree we can see that we have overlapping subproblems so we can use dynamic programming.
We can use the bottom-up approach to solving this problem
We can make a 2d matrix ‘DP’ that stores the states.
dp[0][0] = true or 1. it is because if the length of the pattern and matching string is 0 then, they are equal or they are a match.
We can fill the first row of the DP. The first row of DP tells us that the matching string length is zero, then up till which column the pattern matches the empty string. So we know that it can only happen if the pattern character at that point is ' * ' and if anything else comes other than a ' * ' then we break.
Now, we can start filling the other rows of the DP matrix, if the pattern is ' * ' at j - 1, then either we can use it to match in that case it would be equal to dp[i - 1][j] and if we use the empty string for ' * ' then it is equal to dp[i][j - 1].
If the pattern at j - 1 is not ' * ' then we need check if the characters are equal or pattern character at j - 1 is ' ? ' then dp[i][j] = dp[i - 1][j - 1];
FInally we return dp[s.length()][p.lenght()]

Space Complexity: O(m*n) - For 2d arraysExplanation:

O(M * N), Where M is the length of str and N is the length of pat.

The Dp array takes space M * N

Time Complexity: O(m*n) - For 2d arraysExplanation:

O(M * N), Where M is the length of str and N is the length of pat.

We need to solve each cell of the matrix of size M * N