Last Updated: 1 Apr, 2021

Matching Queries

Hard

Asked in companies

Solve now

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

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

Solve now

Approaches

01 Approach

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

Solve now