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.
Examples:
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:
- Split the given string S by spaces.
- Create a list ‘res‘ to store the ‘N+1’th words in the string.
- Now, iterate through the split string from i = 0.
- Check every (i)th, (i+1)th, . . ., (i+N-1)th indices in every iteration, whether they are equal to the ‘first’, ‘second’, . . ., ‘N’th words respectively or not.
- If yes then append the (N+1)th word to the answer list.
- Return the list storing the words as the required answer.
Below is the implementation for the above idea:
Python3
|
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)