Matching Queries

Hard
0/120
Average time to solve is 45m
profile
Contributed by
7 upvotes
Asked in companies
OracleGoogle inc

Problem statement

You are given an array/list ‘QUERY’ consisting of ‘N’ strings and a string ‘PATTERN’. For each valid integer ‘i’ (0 <= ‘i’ < N), Check whether ‘QUERY[i]’ matches ‘PATTERN’ or not.

‘QUERY[i]’ matches the string ‘PATTERN’, if we can insert some lowercase letters in the ‘PATTERN’ so that it equals the ‘QUERY[i]’.

Your task is to return a boolean array/list of size ‘N’ where the element at index ‘i’ is True, if and only if ‘QUERY[i]’ matches with ‘PATTERN’ otherwise, it is False.

Example : 
Consider ‘QUERY’ = [“Coding”, “CodiNg”, “COdiNG”, “Ninja”, “CNinja”] and string ‘PATTERN’ = “CN”
Then “CN” equals “CodiNg” by inserting lowercase letters “o”, “d”, “i”, and “g” like this -:  “C” + “odi” + “N” + “g” =  “CodiNg”.
 “CN” equals “CNinja” by inserting lowercase letters “i”, “n”  “j” and “a” like this -:  “CN” + “inja” = “CNinja”.
 No other string in ‘QUERY’ can match with “CN” by inserting some lowercase letters.
 Thus, we should return the boolean array -: [False, True, False, False, True].
Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case consists of a single integer ‘N’ representing the size of the list/array ‘QUERY’.

The second line of each test case consists of ‘N’ single space-separated strings representing array ‘QUERY’.

The third line of each test case consists of a single string, ‘PATTERN’.
Output format : 
For each test case, print ‘N’ single space-separated strings, where the ‘i-th’ string will be “True”, if and only if ‘QUERY[i]’ matches with the ‘PATTERN’, Otherwise it will be “False”.

Print the output of each test case in a separate line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 50
1 <= N <= 10^3
1 <= |QUERY[i]| <= 10^3
1 <= |PATTERN| <= 10^3
‘PATTERN’ has only lowercase or uppercase English letters.
‘QUERY[i]’ has only lowercase or uppercase English letters.

Where ‘T’ is the total number of test cases,  ‘N’ is the size of the list/array ‘QUERY’, |QUERY[i]|  is the maximum length of the string in ‘QUERY’ and |PATTERN| is the length of the given string ‘PATTERN’.


Time limit: 1 sec
Sample Input 1 :
2
3
Ce CE Cet
Ce
5
Coding CodiNg COdiNG Ninja CNinja
CN
Sample Output 1 :
True False True
False True False False True
Explanation of Sample Input 1 :
Test case 1:
Here, “Ce” and “Cet” match with the string “Ce”.

Test case 2:
See the problem statement for an explanation.
Sample Input 2 :
2
5
FbK FootBall FooBar foobar FBK
FB
1
code
cd
Sample Output 2 :
False True True False False
True
Hint

Can we use the two-pointers method to check whether a string matches the pattern?

Approaches (1)
Two-pointers.

This approach is straightforward, We one by one check for each ‘i’ whether ‘QUERY[i]’ matches ‘PATTERN’ or not using the algorithm based on two-pointers as described below. 

 

Algorithm

  • Create a boolean list/arr ‘RESULT’ of size ‘N’ and initially, fill it with False.
  • Run a loop where ‘i’ ranges from 0 to ‘N’ and in each iteration do the following -:
    • Initialize two integer variables ‘p’:= 0 and ‘q’:= 0.
    • Run a loop till ‘p’ < |QUERY[i]| (length of QUERY[i]) and in each iteration do the following -:
      • If q < |PATTERN| and QUERY[i][p] = PATTERN[q], then increment ‘q’ by 1.
      • Else If QUERY[i][p] is an uppercase letter then break the loop.
      • Increment ‘p’ by 1.
    • If ‘p’ = |QUERY[i]| and ‘q’ = |PATTERN|, then do RESULT[i]:= True.
  • Return ‘RESULT’.
Time Complexity

O(N*(|S| + |P|)), where ‘N’ is the total number of strings in the ‘QUERY’, |S| and |P| respectively represent the maximum length of the string in list/array ‘QUERY’ and length of the given string ‘PATTERN’.

 

There are ‘N’ strings in the list/array ‘QUERY’, and for each  ‘i’ (0 <= i < N), we iterate over the string QUERY[i] of maximum length |S| by pointer ‘p’ and the string ‘PATTERN’ of length |P| by pointer ‘q’, which takes O(|S| + |N|) time per query. Thus, the overall time complexity will be O(N*(|S| + |P|)),

Space Complexity

O(1)

 

We are using only constant extra space here.

Code Solution
(100% EXP penalty)
Matching Queries
Full screen
Console