Найти все слова из String, присутствующие после заданных N слов
Имея строку S и список lis[] из N слов, задача состоит в том, чтобы найти каждое возможное (N+1) -е слово из строки S так, что «второе» слово идет сразу после «первого» слова, «третье» слово идет сразу после «второго» слова, «четвертое» слово идет сразу после «третьего» слова и так далее.
Примеры:
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]
Подход: Самый простой способ решить проблему:
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.
Следуйте инструкциям, чтобы решить проблему:
- Разбить заданную строку S пробелами.
- Создайте список res для хранения N+1 слов в строке.
- Теперь выполните итерацию по разделенной строке, начиная с i = 0.
- Проверить каждый (i) -й , (i+1) -й , . . ., (i+N-1) -й индекс на каждой итерации, равны ли они 'первому', 'второму', . . ., 'N-го слова соответственно или нет.
- Если да, то добавьте (N+1) -е слово в список ответов.
- Верните список, в котором хранятся слова, в качестве требуемого ответа.
Ниже приведена реализация вышеупомянутой идеи:
Временная сложность: O(N * K * d), где K — размер строки, а d — максимальный размер слова.
Вспомогательное пространство: O(N)