Regular Expression Match

Posted: 16 Jan, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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

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.
Try Problem