Найти все слова из String, присутствующие после заданных N слов

Опубликовано: 26 Февраля, 2023

Имея строку 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)

РЕКОМЕНДУЕМЫЕ СТАТЬИ