Пересечение двух шаблонов со звёздочками
Задача по программированию с проверкой онлайн
- Сложность
- Средняя
- Языки
- Python
- JavaScript
- TypeScript
- Java
- Go
- Темы
- Строки
- Динамическое программирование
Шаблон состоит из латинских букв (заглавные и строчные различаются) и звёздочек *. Строка из букв подходит к шаблону, если каждую звёздочку можно заменить строкой из от нуля до четырёх любых букв так, чтобы шаблон совпал со строкой. Например, к Gone** подходят GoneGirl и GoneTomorrow, но не Gonetomorrow (лишняя буква) и не TheGoneGirl.
Даны два шаблона длиной хотя бы 1. Верните true, если существует строка (возможно, пустая), подходящая к обоим, иначе false.
Ограничения: длина каждого шаблона до 200, звёздочек может быть сколько угодно.
Пример: "Shakes*e", "*peare" → false (звёздочка в начале второго шаблона не покрывает шесть букв Shakes).
Источник: Coding Competitions Archive, kickstart/2017/round_a/pattern_overlap · © Google LLC · Apache-2.0 · условие переведено и дополнено