Minimum Break

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
2 upvotes
Asked in companies
AppleFacebook

Problem statement

You are given an array 'ARR' of strings. Each string contains lowercase English letters only.

String 'P' is said to be compatible with String 'Q' if it is possible to convert String 'P' to String 'Q' by replacing each '*' character in String 'P' with any sequence of characters including the empty sequence.

For example :

Consider P = "a*d" and Q = "abcd"
If we replace '*' with "bc" the resulting string P becomes "abcd" which is equal to Q. Hence, the string P is compatible with String Q.

You are given a string 'S'. Your task is to check whether any such string exists in the array 'ARR' that string 'S' is compatible with.

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer ‘T’ which contains the number of test cases. 

The first line of each test case contains an integer 'N' denoting the number of strings in the array 'ARR'.

The second line of each test case contains 'N' space separated strings denoting the array 'ARR'. 

The third line of each test case contains the string 'S'.
Output Format: 
For each test case, print 1 if any such string exists in the array 'ARR' that string 'S' is compatible with. Otherwise print 0.
Note: 
You do not need to print anything. It has already been taken care of, just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 10 
1 <= |S| <= 100
1 <= |M| <= 100 

Strings 'S' contains lowercase English letters and '*' only. 
String 'M' contains lowercase English letters only.

Where 'M' denotes any element of the array 'ARR', |S| and |M| denotes the length of String 'S' and String 'M' respectively.

Time Limit: 1 sec
Sample Input 1:
2
4
abc abcd ab aa
*b*d 
3
bcs bce bcc
*bc
Sample Output 1:
1
0
Explanation of Sample Input 1:
For the first test case, If we replace the first '*' with 'a' and the second '*' with 'c' the resulting string S becomes 'abcd' which is present in the array 'ARR'. Therefore, the answer is 1 in this case.

For the second test case:
Let's try all the array elements one by one
1) To convert "*bc" into "bcs" we need a '*' at the end of string S which is not present. Hence string S is not compatible with string  "bcs". 
2) To convert "*bc" into "bce" we need a '*' at the end of string S which is not present. Hence string S is not compatible with string "bce".
3) To convert "*bc" into "bcc" we need a '*' at the end of string S which is not present. Hence string S is not compatible with string "bcc". 
We can see that string 'S' is not compatible with any of the array elements. Therefore the answer is 0 in this case.
Sample Input 2:
2
3
abc abd abe
*
bc bce bcs
c**
Sample Output 2:
1
0
Hint

Try to think of a recursive approach to check compatibility between two strings

Approaches (3)
Recursive Approach

First of all, let's define a function checkCompatibility to check compatibility between two strings 'P' and 'Q' which takes 4 arguments the string 'P' the string 'Q', and 2 integer values ‘i’ and ‘j’  to keep track of the index of 'P' and 'Q' respectively.

The idea is pretty straightforward: iterate through 'P' and 'Q' while there is a match between the current character of 'P'  and the current character of 'Q'. If we reach the end of both strings while there is still a match, we will return 1 denoting that the strings are compatible, otherwise, we will return 0. The scan is done by having a pointer each in string 'P' and 'Q'.

 

Below is the detailed algorithm: 
 

  1. Let ‘i’ denote the current index of string 'P' and ‘j’ denote the current index of 'Q'.
  2. If ‘i’ = 'P'.length() and j = 'Q'.length() then return 1.
  3. If ‘j’ = 'Q'.length()
    1. If 'P'[i] = ' * ' then call checkCompatibility ( 'P', 'Q', ‘i’ + 1 , ‘j’ )
    2. Else return 0.
  4. If ‘i’ = 'P'.length () then return 0.
  5. If 'P'[i] = ' * ' then we will return 1 if either  checkCompatibility ( 'P', 'Q', ‘i’ + 1 , ‘j’ ) or checkCompatibility ( 'P', 'Q', ‘i’  , ‘j’ + 1) returns 1, otherwise we will return 0.
  6. If 'P'[i] = 'Q'[j] we will return checkCompatibility ( 'P', 'Q', ‘i’ + 1 , ‘j’ + 1) otherwise we will return 0.

Now we will iterate over the Array ‘ARR’ and call checkCompatibility ( ‘S’, ‘M’, 0, 0 ) for each of the array element ‘M’ and we will return 1 if we get 1 as output during any iteration. Otherwise we will return 0.

Time Complexity

O(N * 2^max(|S|, |M|), where |S| is the size of String S and |M| is the size of any array element and N denotes the number of elements in the array.

 

In the worst case, when we have ‘*’ at alternating places in String P we will recursively call the checkCompatibility function 2^max(|S|, |M|) times for each of the N array elements. Hence, the overall time complexity becomes O(N * 2^max(|S|, |M|).

Space Complexity

O(max(|S|, |M|)),  where |S| is the size of String S and |M| is the size of any array element.

 

In the worst case, when we have ‘*’ at alternating places in String P we will recursively call the checkCompatibility function 2^max(|S|, |M|) times and therefore the recursion stack will take O(max(|S|, |M|)) extra space. Hence, the overall space complexity is O(max(|S|, |M|)). 

Code Solution
(100% EXP penalty)
Minimum Break
Full screen
Console