Check If Given Words Are Present In A String
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

Question

Check If Given Words Are Present In A String

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

Accepted Answer

Brute Force

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.

Space Complexity: OtherExplanation:

O(N), where ’N’ is the number of words in ‘wordList’

The size of the result array is of order ‘N’.

Time Complexity: OtherExplanation:

O(N*|S|*|W|), where ’N’ is the number of words in ‘wordList’, |S| is the length of string ‘S’, and |W| is the maximum length of words present in ‘wordList’.

Here, we will have three nested loops, and in the worst case the outermost loop runs ‘N’ time, and the middle loop runs |S| time and the innermost loop runs |W| times. This time complexity should be of order O(N*|S|*|W|).

Accepted Answer

Using KMP or Rabin-Karp

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.

Space Complexity: OtherExplanation:

O(|W| + N), where ‘|W| is the length of the longest word in ‘wordList’ and string and ‘N’ is the number of words in ‘wordList’.

The preprocessing step in KMP takes the space of order ‘|W|’ and the result vector takes space of order ‘N’.

Time Complexity: OtherExplanation:

O(N * (|S| + |W|)), where ’N’ is the number of words in ‘wordList’, |S| is the length of string ‘S’, and |W| is the maximum length of words present in ‘wordList’.

Time taken by KMP or Rabin-Karp is of order |S| + |W|.

Accepted Answer

Using Trie

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.

Space Complexity: OtherExplanation:

O(N*|W|), where ’N’ is the number of words in ‘wordList and |W| is the maximum length of the longest word present in ‘wordList’.

Trie uses space of order ‘N*W’

Time Complexity: OtherExplanation:

O(N*|W| + |S|*|W|), where ’N’ is the number of words in ‘wordList’, |S| is the length of string ‘S’, and |W| is the length of the longest word present in ‘wordList’.

Time taken to insert ‘N’ words in the trie is of order N*|W|, and it will take the time of order |S|*|W| to check whether each word is present in the string ‘S’ or not using trie.

Accepted Answer

Check If Given Words Are Present In A String
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

Accepted Answer

Check If Given Words Are Present In A String
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:

Input Format :

Output Format :

Note :

Constraints :

Popular interview questions of System Engineer

Top HR questions asked in Tata Group System Engineer