Удалить последнее вхождение слова из данной строки предложения

Опубликовано: 22 Сентября, 2022

Даны две строки S и W размеров N и M соответственно, задача состоит в том, чтобы удалить последнее вхождение W из S . Если W не встречается в S , выведите S как есть.

Примеры:

Input: S = “This is GeeksForGeeks”, W=”Geeks”
Output: This is GeeksFor
Explanation:
The last occurrence of “Geeks” in the string is substring over the range [16, 20].

Input: S=”Hello World”, W=”Hell”
Output: o World
Explanation:
The last occurrence of “Hell” in the string is substring over the range [0, 3].

Подход: проблему можно решить, перебирая каждый индекс i строки S и проверяя, существует ли подстрока, начинающаяся с индекса i , который равен строке W. Выполните следующие шаги, чтобы решить проблему:

  • Если N меньше M , выведите S , так как W не может быть в S .
  • Инициализируйте переменную i как NM для перебора строки S .
  • Повторяйте, пока i не станет больше 0 , и выполните следующие шаги:
    • Проверить, равна ли подстрока в диапазоне [i, i+M-1] строке W или нет. Если оно равно, то удалить подстроку в диапазоне [i, i+M-1] из строки S , а затем разбить.
    • В противном случае продолжайте.
  • Наконец, после выполнения вышеуказанных шагов выведите строку S в качестве ответа.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(M*N)
Вспомогательное пространство: O(1)

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