No products in the cart!
Please make your choice.View all catalog
Given a string S and a list lis of N number of words, the task is to find every possible (N+1)th word from string S such that the ‘second’ word comes immediately after the ‘first’ word, the ‘third’ word comes immediately after the ‘second’ word, the ‘fourth’ word comes immediately after the ‘third’ word and so on.
Input: S = “Siddhesh is a smart guy the city he lives in is a smart city”, lis: [“is”, “a”, “smart”]
Output: [guy, city]
Explanation: Here the two sequences where the words occur
just as the pattern mentioned are.
- is a smart guy
- is a smart city
Hence we found ‘guy’ and ‘city’ as the desired words.
Input: S = “David loves to play and David loves to write sometimes”, lis: [“loves”, “to”]
Output: [play, write]
Approach: The simplest way to solve the problem is:
Break the whole string into words separated by spaces and Iterate over these words and match (i)th, (i+1)th, . . . (i+N-1)th word with the first, second, . . ., Nth words given, If the words matched store the (i+N)th word in a list.
Follow the steps to solve the problem:
Below is the implementation for the above idea:
Time Complexity: O(N * K * d) where K is the size of the string and d is the maximum size of a word
Auxiliary Space: O(N)