Check if the Word is present in Sentence or not

Easy
0/40
Average time to solve is 15m
26 upvotes
Asked in companies
AmazonWalmartIntuit

Problem statement

You have been given a sentence ‘S’ in the form of a string and a word ‘W’, you need to find whether the word is present in the given sentence or not. The word must be present as a complete string in the sentence and not a substring of some other word.

Note:

1. All the characters in the string and the word are in lowercase.
2. Length of the sentences and the words will always be greater than zero.
3. Words in the sentence will be separated by spaces.
Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line of the input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains the sentence ‘S’.

The second line of each test case contains the word ‘W’.

Output Format :

The only line of output of each test case should print “Yes” if the word ‘W’ is present in the sentence ‘S’, else print “No”.

The output of each test case will be printed in a separate line.

Note: You are not required to print the expected output; it has already been taken care of. Just implement the function.

Constraints :

1 <= T <= 50
1 <= |S|, |W| <= 10000

Where ‘T’ is the number of test cases, ‘S’ and ‘W’ are strings as described in the problem statement.

Time limit: 1 sec
Sample Input 1:
2
abaa ba
abaa
coding is fun
not
Sample Output 1:
Yes
No
Explanation for Sample Input 1:
For the first input,  “abaa” is present in the sentence.
For the second input, “not” is not present in the sentence.
Sample Input 2:
2
the quick brown fox
brown
welcome to coding ninjas
ninja
Sample Output 2:
Yes
No
Explanation for Sample Input 2:
For the first input, “brown” is present in the sentence.
For the second input, the word “ninja” is not present in the sentence.
Hint

Try the simplest possible way.

Approaches (2)
Brute Force

The basic idea of this approach is to check each word of the given sentence ‘S’ if it matches with the given word ‘W’.


 

Consider the following steps:

  1. Start iterating through each character of sentence string ‘S’ using a variable ‘i’ such that 0 <= ‘i’ < |S|
    • Create a string “temp” which stores the current word.
    • Add all the subsequent characters of the sentence till space is detected or if all end of the string is reached.
    • Check if the word ‘W’ matches with “temp”. Return true if it matches.
  2. After the loop ends return false because the word is not present in the sentence.
Time Complexity

O(|S|), where |S| is the length of the string.

 

Since we are iterating through the input sentence string ‘S’ once and checking if the word matches with the given word ‘W’. So the overall time complexity will be O(|S|). Please refer here for more details link

Space Complexity

O(|S|), where |S| is the length of the string.

 

Since we are using a variable to store the words of the sentence string and in the worst case, the whole string can be a single word. So the overall space complexity will be O(|S|).

Code Solution
(100% EXP penalty)
Check if the Word is present in Sentence or not
Full screen
Console