Check If Given Words Are Present In A String

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’.

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’.

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’.

Test case 1: Here String ‘S’ is “This is a large String” and ‘wordList’ is [“This”, “this”, “is”, “age”] The word “This” is present from index ‘0’ to index ‘3’ in ‘S’. The word “this” is not present in ‘S’. The word “is” is present from index ‘2’ to index ‘3’’ and from ‘5’ to index ‘6’ in ‘S’. The word “age” is not present in ‘S’. Note: All words are case sensitive and we consider 0 based indexing in 'S'. Test case 2: Here String ‘S’ is “ILikeCodingNinjas” and ‘wordList’ is [“Ninja” “Coding” “Code”] The word “Ninja” is present from index ‘11’ to index ‘15’ in ‘S’. The word “Coding” is present from index ‘5’ to index ‘10’ in ‘S’. The word “Code” is not present in ‘S’.

Test case 1: Here String ‘S’ is “This is String” and ‘wordList’ is [“This”, “String” ] The word “This” is present from index ‘0’ to index ‘3’ in ‘S’. The word “String” is present from index ‘8’ to index ‘13’’ in ‘S’. Test case 2: Here String ‘S’ is “Code Infy” and ‘wordList’ is [“C” “I” “F”] The word “C” is present at index ‘0’ ’ in ‘S’. The word “I” is present at index ‘5’ in ‘S’. The word “F” is not present in ‘S’. Test case 3: Here String ‘S’ is “Coding” and ‘wordList’ is [“ CodingNinjas”] The word “CodingNinjas” is not in ‘S’.

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.

Time Complexity

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|).

Space Complexity

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

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

Check If Given Words Are Present In A String

Problem statement

Sample Input 1 :

Sample Output 1 :

Explanation Of Sample Input 1 :

Sample Input 2 :

Sample Output 2 :

Explanation Of Sample Input 2 :