Перетасовка разрезами

Сложная

Строку перетасовывают так: - если в ней один символ, ничего не происходит; - иначе её разрезают в любом месте на два непустых куска x и y (так что строка равна x + y), по желанию меняют куски местами (получается y + x) и затем так же перетасовывают каждый кусок отдельно. Даны строки start и goal одинаковой длины. Верните true, если при каком-то выборе разрезов и обменов из start получается goal, и false иначе.

Пример 1

start="stone", goal="tones" → True

Режем "stone" на "s" и "tone" и меняем куски местами: "tone" + "s" = "tones". Дальше куски можно оставить как есть.

Пример 2

start="abcd", goal="bdac" → False

Первый разрез даёт "a"+"bcd", "ab"+"cd" или "abc"+"d". Чтобы получить "bdac", один из кусков должен состоять из тех же букв, что начало или конец "bdac" той же длины ("b", "bd", "bda" или "c", "ac", "dac"). Ни один вариант не подходит, поэтому ответ false.

Пример 3

start="z", goal="z" → True

Ограничения

1 ≤ len(start) ≤ 30
len(goal) = len(start)
Строки состоят из строчных латинских букв

Встречал эту задачу на настоящем собесе?

Решили0

Пробовали0

Отправок0

Принято—

Темы

String Dynamic Programming

Вход

start="stone", goal="tones"

Ожидается

True

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 100 тестов на сервере, включая скрытые.