Last Updated: 9 Dec, 2020
Check If Given Words Are Present In A String
Hard
Asked in companies
Given a string 'S' and a list 'wordList' that consists of 'N' distinct words. Let 'Wi' denote word at index 'i' in 'wordList'. For each word 'Wi' in 'wordList', you need to determine whether it is present in string 'S' or not. Return a boolean array, where a boolean value at index ‘i’ represents whether the word ‘Wi’ is present in the string ‘S’ or not.
Input Format :
The first line of input contains an integer ‘T’ denoting the number of test cases.
The next ‘3*T’ lines represent the ‘T’ test cases.
The first line of each test case contains the string ‘S’.
The second line of each test contains an integer ‘N’ representing the number of words in the ‘wordList’.
The third line of each test case contains the ‘N’ space-separated strings representing the words in the ‘wordList’.
Output Format :
For each test case, print a boolean array where the value at index ‘i’ is ‘True’ if the word at index ‘i’ in the ‘wordList’ is present in string ‘S’ Otherwise, it is ‘False’.
Note :
1. String ‘S’ consists of lowercase, uppercase alphabets, and spaces.
2. String ‘Wi’ consists of lowercase and uppercase alphabets only.
3. The word, ‘Wi’ is case sensitive.
4. You can’t use language-built-in string-matching methods.
5. Don’t print anything, just return the boolean array determining the presence or absence of the words present in ‘wordList’.
Constraints :
1 <= T <= 50
1 <= |S| <= 10^3
1 <= N <= 10^3
1 <= |W| <= 10
Where ‘|S|’ denotes the length of string and |W| denotes the maximum length of the word present in ‘wordList’.
Time limit: 1 sec
Approaches
- This is an iterative approach.
- Make a boolean vector ‘result’ of size ‘N’. Initially, all the elements of this vector should be ‘False’.
- Run a loop where ‘i’ ranges from 0 to ‘N-1’ and for each word ‘Wi‘ present at ‘ith’ index of ‘wordList’, we will check whether ‘Wi‘ is a substring of string ‘S’ or not. This can be done as follow-:
1. If the length of ‘Wi’ is greater than ‘S’, then it cannot be a substring of ‘S’.
2. Otherwise, we need to run a nested loop where the outer loop ranges ‘j’ from 0 to |S|-|Wi| and the inner loop ranges ‘ k’ from 0 to |Wi|-1. And we need to check whether there exist any index ‘ j’ in ‘S’ such that for all ‘k’ from 0 to |Wi|-1, character at ‘j+k’ index in ‘S’ is the same as ‘kth’ character of string ‘Wi’. If such index ‘j’ exists only then ‘Wi’ is a substring of ‘S’.
3. If ‘Wi’ is a substring of ‘S’. then set result[i] = true. - Return the result array.
KMP algorithm or Rabin-Karp algorithm can search for a substring in a string in linear time. We can use it to optimize the run time of our solution.
- Make a boolean vector ‘result’ of size ‘N’. Initially, all elements of this vector should be ‘False’.
- Run a loop where ‘i’ ranges from 0 to ‘N-1’ and for each word ‘Wi‘ present at ‘ith’ index of ‘wordList’, we will check whether ‘Wi‘ is a substring of string ‘S’ or not. This can be done as follow-:
1 If the length of ‘Wi’ is greater than ‘S’, then it cannot be a substring of ‘S’.
2. Otherwise, use either KMP or Rabin-Karp to check whether the ‘Wi’ is a substring of ‘S’ or not.
3. If ‘Wi’ is a substring of ‘S’. then set result[i] = true.
- Return the result array.
Trie, also known as ‘prefix tree’ is a tree-like data structure where nodes of the tree store entire alphabets and strings can be retrieved by traversing down a branch part of the tree. Trie allows us to search for any key in O(key_length) time.
Here, we can build a trie containing all the words in ‘wordList’ and then iterate through string ‘S’ and check whether any part of string ’S’ is present in the trie or not as mentioned below.
- Make a boolean vector ‘result’ of size ‘N’. Initially, all elements of this vector should be ‘False’.
- Run a loop where ‘i’ ranges from 0 to ‘N-1’ and insert each word ‘Wi‘ present at ‘ith’ index of ‘wordList’ in the trie. Here we need to also store indexes of words in the trie. This can be done by marking the end of a word with its index in ‘wordList’.
- Run a loop where ‘i’ ranges from 0 to |S|-1, and for each ‘i’ -:
1. Initialize a pointer ‘j’ at ‘i’ and increment j till prefix S[i..j] is present in the trie. If prefix S[i..j] is not present then break the inner loop.
2. If S[i..j] makes a complete word present in trie, we find its index and update ‘result[idx]’ = true, where ‘idx’ is the index of words S[i..j] in ‘wordList.’ - Return the result array.