Ninja and Index Pairs

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
10 upvotes
Asked in companies
eBayGoldman Sachsalibaba

Problem statement

Ninja has been given a string ‘TEXT’ and an array/list of strings ‘WORDS’ of size ‘N’. Ninja has to print all index pairs (‘i’, ‘j’) such that the substring of ‘TEXT’ is present in the ‘WORDS’.

Note: 
Ninja has to return all the index pairs (‘i’, ‘j’) in sorted order, i.e., sort them by the first element of the pair, i.e., ‘i’.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case will contain a single space-separated string ‘TEXT’ which represents the value of ‘TEXT’.

The next line of each test case contains a single space-separated integer ‘N’ denoting the size of ‘WORDS’.

The next line of each test case contains ‘N’ space-separated integers representing the values of ‘WORDS’.
Output Format: 
For each test case, print all index pairs (‘i’, ‘j’) such that the substring of ‘TEXT’ is present in the ‘WORDS’ in sorted order according to the first element of the pair.

Output for every test case will be printed in a separate line.
Note: 
You don’t need to print anything; It has already been taken care of.
Constraints: 
1 <= ‘T’ <= 50    
1 <= | ‘TEXT’ | <= 100
1 <= ‘N’ <= 20
1 <= |’WORDS[i]’ | <= 50  

Where ‘T’ is the number of test cases, 'N' is the size of array/vector ‘WORDS’, |’WORDS[i]’| represents the size of each word in ‘WORDS’ and |’TEXT’| represents the size of input string ‘TEXT’|.

Time limit: 1 sec
Sample Input 1:
1
abcdefcd
2
cd abc
Sample Output 1:
0 2
2 3
6 7
Explanation of sample input 1:
In the first test case:
For the string “cd” the index of this substring in the given ‘TEXT’ string is (2, 3) and (6, 7).
For string “abc” index of this substring in given ‘TEXT’ string is (0, 2).
Hence the sorted order of these indices is (0, 2), (2, 3), and (6, 7).
Sample Input 2:
1
codingninjas
4
cod co c nar
Sample Output 2:
0 0
0 1
0 2
Explanation for sample input 2:
In the first test case:
For string “cod” index of this substring in given ‘TEXT’ string is (0, 2)
For string “co” index of this substring in given ‘TEXT’ string is (0, 1).
For string “c” index of this substring in given ‘TEXT’ string is (0, 0)
For string “nar” there is not an index present in this string ‘TEXT’.
Hence the sorted order of these indices is (0, 0), (0, 1), and (0, 2).
Hint

Can you think of a simple iteration on ‘WORDS’?

Approaches (2)
Brute Force

The basic idea is to first iterate on the ‘WORDS’ array/list and then for each word check in the string ‘TEXT’ whether this string is present or not. If the word is present then put all indexes in a list/vector ‘allIndexPair’ and at the end sort this list/vector and return this.

 

The steps are as follows:

 

  1. Declare a list/vector ‘allIndexPair’ as discussed above.
  2. Run a loop on the ‘WORDS’ array/list:
    • If the current word is present in the ‘TEXT’ string:
      • Add all these indexes in ‘allIndexPair’.
  3. Sort this ‘allIndexPair’ according to the first element of the pair.
  4. Finally, return the ‘allIndexPair’.

 

For example:

‘TEXT’ = “aaa”

‘WORDS’ = [a aa aaa]

For string “a’ indices are (0,0), (1,1), (2,2).

For string “aa’ indices are (0,1), (1,2).

For string “aaa’ indices are (0,2).

Time Complexity

O(N^2 * log(N) + (N*L*X)), where ‘N’ is the size of ‘WORDS’, ‘L’ is the length of ‘TEXT’, and ‘X’ is the length of the longest word in ‘WORDS’.

 

Because first, we are iterating over the ‘WORDS’ array/list and then check this word in the string ‘TEXT’ it takes O(N * L * X ) time. Then, we are sorting the ‘allIndexPair’. In the worst-case size of ‘allIndexPair’ is (N*(N+1)) / 2 and therefore sorting takes O(N^2 * log(N)) time. Hence, the overall time complexity is O(N^2 * log(N) + (N*L*X)).

Space Complexity

O(N^2), where ‘N’ is the size of ‘WORDS’.

 

Because we are storing all the indices in  ‘allIndexPair’ list/vector. Hence the space complexity is O(N^2).

Code Solution
(100% EXP penalty)
Ninja and Index Pairs
Full screen
Console