Prefix Suffix Search

Easy
0/40
Average time to solve is 20m
profile
Contributed by
16 upvotes
Asked in company
Amazon

Problem statement

Ninja has to implement a new data structure, ‘PRE_SUF_SEARCH’. This data structure allows searching the word by prefix and suffix that is present in ‘PRE_SUF_SEARCH’.

Ninja has to implement two functions:

1) wordFilter(‘WORDS’): Add this ‘WORDS’ array/list into ‘PRE_SUF_SEARCH’.
2) find(‘PREFIX’, ‘SUFFIX’): Return the index of the word that is present in ‘PRE_SUF_SEARCH’ having prefix as ‘PREFIX’ and the suffix as ‘SUFFIX’.

Note:

1) If there is more than one valid index in ‘PRE_SUF_SEARCH’ for the word, then return the largest possible index.
2) If there is no such word present in the ‘PRE_SUF_SEARCH’, then return -1.
3) ‘WORDS’ array/list contains only lowercase English alphabets.

For example:

‘PRE_SUF_SEARCH’ = [“apple”, “mango”, “banana”].
Query_1: find(‘a’, ‘e’).

We have to find the index of the largest possible word that starts with ‘a’ and ends with ‘e’.

Here we have only one word ‘apple’ present in ‘PRE_SUF_SEARCH’ and satisfy this condition. So we return 0.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer ‘T’ which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case contains an integer ‘N’ representing the number of words in the ‘WORDS’.

The next line of each test case contains ‘N’ single space-separated words representing the elements of ‘PRE_SUF_SEARCH’.

The next line of each test case contains an integer ‘Q’ representing the number of times the function find(‘PREFIX’, ‘SUFFIX’) call.

The next line of each test case contains two words representing the ‘PREFIX’ and ‘SUFFIX’.
Output Format : 
For each test case, print a single line containing a single integer denoting the largest index of the word that satisfies the above conditions.

The output of each test case will be printed in a separate line.
Note: 
You don’t need to print anything; It has already been taken care of. Just implement the given function.


Constraints: 
1 <= ‘T’ <= 100
1 <= ‘N’ <= 10000
1 <= | ‘WORDS[i]’ | <= 10
1 <= ‘Q’ <= 10000
1 <= | ‘PREFIX’ |, | ‘SUFFIX’ | <= 10

Where ‘T’ denotes the total number of test cases, ‘N’ represents the number of words in ‘WORDS’, and | ‘ WORDS’ | indicates the size of each word, ‘Q’ represents the number of times the function find(‘PREFIX’, ‘SUFFIX’) call and ‘PREFIX’ and ‘SUFFIX’ represents the prefix and suffix of the word that is to be searched in ‘PRE_SUF_SEARCH’.

Time limit: 1 sec.
Sample Input 1:
1
3
cat bat rat
3
ca t
b t
rr t
Sample Output 1:
0
1
-1
Explanation of sample input 1:
For sample test case 1:
For query 1,  "cat" has the prefix "ca" and suffix ‘t'.
For query 2,  "bat" has the prefix 'b' and suffix 't'.
For query 3,  there is not a single word present in the 'PRE_SUF_SEARCH' that has the prefix "rr".
Sample Input 2:
1
4
coding ninjas is best for coding platform
2
co ng
bes st
Sample Output 2:
5
3
Explanation for sample input 2:
For sample test case 1:
For query 1,  "coding" has the prefix "co" and suffix “ng”. This word is present at 0 index and 5 index so we return 5 index which is the largest index among them.
For query 2,  "best" has the prefix “bes” and suffix “st”.
Hint

Can you think of Hashing?

Approaches (2)
Hashing

First, we will implement the wordFilter function. We will find all the prefixes and suffixes and concatenate them by adding a special character i.e ‘#’ between them. Then store this word in the HashMap ‘ALL_POSS_PRE_SUF_COMB’ with the index number as the value of this HashMap. 

 

Then we implement the find function. We simply check if the word ‘PREFIX’ + ‘#’ + ‘SUFFIX’ is present in the HashMap ‘ALL_POSS_PRE_SUF_COMB’ or not. If this word is not present in the HashMap return -1.

 

Here is the algorithm:

 

  1. Declare a HashMap ‘ALL_POSS_PRE_SUF_COMB’ in which we store all words of the ‘WORDS’ array/list.
  2. wordFilter(‘WORDS’)
    • Run a loop for ‘i’ = 0  to the length of the ‘WORDS’:
      • Run a loop for ‘j’ = 0 to the length of the ‘WORDS[i]’:
        • Run a loop for ‘k’ = 0 to the length of the ‘WORDS[i]’:
          • Add substring of ‘WORDS[i] from ‘0’ to ‘j’ + ‘#’ + substring of ‘WORDS[i] from (‘WORDS’ length - ‘k’) to the end of this word into  ‘ALL_POSS_PRE_SUF_COMB’ as a key and ‘i’ as value.
  3. find(‘PREFIX’, ‘SUFFIX’)
    • If the word ‘PREFIX’ + ‘#’ + ‘SUFFIX’ is present in the HashMap ‘ALL_POSS_PRE_SUF_COMB’:
      • Return value that is present at this word.
    • Else:
      • Return -1.
         
Time Complexity

For worldFilter(‘WORDS’) Function:

O(N * (L ^ 3)) where ‘N’ represents the length of the array/list ‘WORDS’. ‘L’ represents the length of the longest word.

 

Since we are iterating through the ‘WORDS’ once and inside it we are using two nested loops till the length of the current word and then we are extracting the substring of the current word. Hence the overall time complexity is O(N * (L ^ 3)). 


 

For find(‘PREFIX’, ‘SUFFIX’) Function:

O(1) 

 

Since the search function for a HashMap takes constant time. Hence the overall time complexity is O(1).


 

Space Complexity

O(N * (L ^ 2)) where ‘N’ represents the length of the array/list ‘WORDS’. ‘L’ represents the length of the longest word.

 

Because we are storing all possible combinations of each word of array/list ‘WORDS’ in a HashMap ‘ALL_POSS_PRE_SUF_COMB’. Hence the overall space complexity is O(N * (L ^ 2)). 

Code Solution
(100% EXP penalty)
Prefix Suffix Search
Full screen
Console