Проверьте, можно ли сделать заданные строки равными, вставив не более 1 строки

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

Имея два предложения S1 и S2 , задача состоит в том, чтобы проверить, можно ли сделать предложения равными, вставив не более одного предложения (возможно, пустого) в любое из двух предложений.

Примеры:

Input : S1 = “Start practicing on GeeksforGeeks”, S2 =”Start GeeksforGeeeks”   
Output : 
True
Explanation: “practicing on” can be inserted between “Start” and “GeeksforGeeks” in s2 to make it equal to S1.

Input: S1= “New Delhi is capital of INDIA”, S2 = “is capital of”   
Output: 
False

Подход: В решении проблемы помогают следующие наблюдения:

  • Если размеры двух предложений равны, но сами они неодинаковы, их нельзя сделать равными.
  • После удаления самого длинного общего префикса и самого длинного общего суффикса двух предложений, если хотя бы одно из них пустое, это означает, что их можно сделать равными.

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

  • Проверьте, равны ли размеры S1 и S2 . Если они равны, сделайте следующее:
    • Если S1 равно S2 , вернуть true .
    • В противном случае вернуть false .
  • Инициализируйте две очереди X и Y .
  • Вставьте все слова S1 в X .
  • Вставьте все слова S2 в Y .
  • В то время как фронты X и Y одинаковы, выталкивайте из фронтов X и Y .
  • В то время как спины X и Y одинаковы, выскочите из спинок X и Y .
  • Проверьте, не является ли какой-либо из X или Y пустым. Если какой-либо из них пуст, верните true .
  • В противном случае вернуть false .

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

Временная сложность: O(N+M), где N и M — размеры S1 и S2 соответственно.
Вспомогательное пространство: O(N+M)

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