Last Updated: 1 Apr, 2021
Prefix Suffix Search
Easy
Asked in company
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.
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.
Approaches
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:
- Declare a HashMap ‘ALL_POSS_PRE_SUF_COMB’ in which we store all words of the ‘WORDS’ array/list.
- 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.
- Run a loop for ‘k’ = 0 to the length of the ‘WORDS[i]’:
- Run a loop for ‘j’ = 0 to the length of the ‘WORDS[i]’:
- Run a loop for ‘i’ = 0 to the length of the ‘WORDS’:
- 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.
- Return -1.
- If the word ‘PREFIX’ + ‘#’ + ‘SUFFIX’ is present in the HashMap ‘ALL_POSS_PRE_SUF_COMB’:
We declare an array/list ‘ALL_INPUT_WORDS’ in which we store all words in the wordFilter function.
Then in the find function, we traverse the ‘ALL_INPUT_WORDS’ from reverse order and check for each word that it contains ‘PREFIX’ as a prefix and ‘SUFFIX’ as a suffix.
Here is the algorithm:
- Declare an array/list ‘ALL_INPUT_WORDS’ as discussed above.
- wordFilter(‘WORDS’)
- Store ‘WORDS’ into ‘ALL_INPUT_WORDS’.
- find(‘PREFIX’, ‘SUFFIX’)
- Run a loop from ‘i’ length of ‘ALL_INPUT_WORDS’ - 1 to 0:
- If the prefix of the current word is equal to ‘PREFIX’ and suffix of the current word is equal to ‘SUFFIX’:
- Return ‘i’.
- Finally, return -1.