Ваша цель: Учитывая строку скобок, выведите минимальное расстояние Дамерау-Левенштейна, необходимое для преобразования входной строки в строку, в которой скобки сбалансированы.
вход
Входная строка будет содержать только скобки и никаких других символов. То есть это комбинация любых символов в (){}[]<>
. Вы можете принять ввод в виде строки или массива символов. Вы не можете делать какие-либо другие предположения относительно входной строки; он может быть произвольно длинным (до максимального размера, поддерживаемого вашим языком), он может быть пустым, скобки уже могут быть сбалансированы и т. д.
Дамерау-Левенштейн Расстояние
Расстояние Дамерау-Левенштейна между двумя строками - это минимальное количество вставок, удалений, односимвольных подстановок и транспозиций (перестановок) двух соседних символов.
Выход
Выходными данными должно быть минимальное расстояние Дамерау-Левенштейна между входной строкой и строкой, в которой сопоставляются скобки. Вывод должен быть числом , а не полученной сбалансированной строкой.
Пара скобок считается "совпавшей", если открывающая и закрывающая скобки расположены в правильном порядке и в них нет символов, например
()
[]{}
Или если каждый подэлемент внутри него также совпадает.
[()()()()]
{<[]>}
(()())
Подэлементы также могут быть вложены в несколько слоев.
[(){<><>[()]}<>()]
<[{((()))}]>
(Спасибо @DJMcMayhem за определение)
Тестовые случаи
Input Possible Balanced Output
Empty Empty 0
[](){}<> [](){}<> 0
[(){}<> [(){}<>] 1
[(]) []() 1
[[[[[[[[ [][][][] 4
(](<>}[>(}>><(>(({}] ()(<>)[(<><>){}] 7
>]{])< []{()} 3
([)}}>[ (){}<> 4
{<((<<][{{}>[<) <>(<<[]>{}>[]) 5
{><({((})>}}}{(}} {<><({()})>}{}{()} 4
(](<)>}[>(}>>{]<<(]] (<()<><<>()>>[])<()> 9
}})( {}() 2
(Спасибо @WheatWizard за решение половины тестовых случаев)
Это код-гольф , побеждает меньше байтов!
Ваши материалы должны быть тестируемыми, то есть они должны выводить результат для каждого теста в течение не более часа.
[<>]
и[]<>
или<>
Ответы:
Сетчатка,
254252264248240232267 байтСпасибо @AnthonyPham, @officialaimm и @MistahFiggins за указание на ошибки
Попробуйте онлайн!
Решение без грубой силы! Он работает для всех тестовых случаев, и даже обнаружил ошибку в одном.
-2 байта благодаря @MartinEnder (
${4}
для$+
)+12 байт для учета дополнительных случаев обмена
-16 байтов за счет лучшего использования классов символов
-8 байт, сняв ненужное ограничение на обмен. Это также исправило ошибку :)
-10 байт путем объединения логики обмена в одно регулярное выражение
+2 байта для учета последовательных перестановок
+ много для различных исправлений ошибок **
Объяснение:
T`[]()`:;'"
используется для замены специальных типов кронштейнов для удобства. Во-первых, мы рекурсивно заменяем все совпадающие скобки-
,AB
или в69
зависимости от того, являются ли они смежными или нет.Затем полезная «замена» выполняется путем удаления новых совпадающих скобок и добавления a
1
в начало строки. Мы также заменим-
на пустую строку, так как она только что использовалась для замены выше.Затем мы пытаемся «заменить», удаляя пары несопоставленных скобок, которые не перекрывают уже сопоставленные скобки, и добавляя
1
к строке.Наконец,
\W|6B|1
подсчитывает все оставшиеся одиночные скобки плюс число1
s.** В настоящее время я работаю над более короткой версией, которая использует функции разделения строк в Retina, хотя столкнулась со значительной проблемой, поэтому это может занять довольно много времени.
источник
${4}
может быть сокращено до$+
. Мне очень любопытно, почему это гарантированно сработает.[{][}] [] [[][][][][][]] [][][][][][][][][][][][]
, вы можете просто поменять местами}
первую пару скобок и сбалансировать их. Интервал используется, чтобы сделать ввод немного более читабельным. Вы вывели 3, но это действительно должно быть одно.[{]}
возвращается 1, но[{][]}
возвращается 2.Brain-Flak , 1350 байт
Попробуйте онлайн!
При сравнении с постоянной скоростью и разыменовании указателя этот алгоритм равен O (n 3 ). К сожалению, Brain-Flak не имеет ни одного из них, поэтому вместо этого эта программа выполняется за O (n 5 ). Самый длинный тестовый случай занимает около 15 минут.
Упрощение результатов
Чтобы убедиться, что мой алгоритм работает, нам нужно показать некоторые результаты, которые значительно сокращают пространство поиска. Эти результаты основаны на том факте, что целью является целый язык, а не одна конкретная строка.
Никаких вставок не требуется. Вместо этого вы можете просто снять скобку, которой в конечном итоге будет соответствовать вставленный символ.
Вам никогда не нужно будет снимать скобку, а затем поменять местами двух соседей. Чтобы убедиться в этом, предположим , что без потери общности , удаленный кронштейн
(
, поэтому мы трансформируемa(c
кca
в два этапа. Изменяяc
и вставляя копию, мы можем достичьca()
в два этапа без обмена. (Эта вставка может быть удалена с помощью вышеуказанного правила.)Один и тот же кронштейн никогда не потребуется менять дважды. Это стандартный факт о расстоянии Дамерау-Левенштейна в целом.
Еще один упрощающий результат, который я не использовал, потому что их учет будет стоить байтов:
Алгоритм
Когда любая строка уменьшается до сбалансированной строки, будет выполнено одно из следующих действий:
k
(возможно, после замены одной или обеих из них).k
.Во втором случае кронштейн в положении
k
мог поменяться с одним из его соседей. В любом из последних двух случаев строка между (возможно, новой) первой скобкой и скобкой, которая начиналась в позиции,k
должна быть отредактирована в сбалансированную строку, как и строка, состоящая из всего, что послеk
.Это означает, что может быть использован подход динамического программирования. Поскольку заменяемая скобка не должна заменяться снова, нам нужно только рассмотреть смежные подстроки, а также подпоследовательности, образованные удалением второго символа и / или предпоследнего символа из такой подстроки. Следовательно, есть только O (n 2 ) подпоследовательностей, которые нам нужно рассмотреть. Каждый из них имеет O (n) возможных способов сопоставления (или удаления) первой скобки, поэтому алгоритм будет иметь O (n 3 ) при указанных выше условиях.
Структура данных
Правый стек включает скобки из исходной строки, по два байта на скобку. Первая запись определяет всю скобку и выбирается таким образом, чтобы совпадающие скобки имели разницу ровно 1. Вторая запись определяет только, является ли она открывающей или закрывающей скобкой: это определяет, сколько изменений требуется для сопоставления двух скобок. друг друга. Никакие неявные нули ниже этого никогда не делаются явными, так что мы можем использовать,
[]
чтобы получить общую длину этой строки.Каждая рассматриваемая подстрока представлена двумя числами в диапазоне от 0 до 2n: одна для начальной позиции и одна для конца. Интерпретация выглядит следующим образом:
2k
будет начинаться с позицииk
(с 0 индексами), а второй символ не удаляется.2k+1
будет начинаться с позицииk
, а второй символ удаляется из-за того, что он поменялся местами.2k
конце, заканчивается непосредственно перед положениемk
(т. Е. Диапазон включается слева и справа).2k-1
конце, заканчивается непосредственно перед положениемk
, и предпоследний символ удаляется из-за того, что он поменялся местами вправо.Некоторые диапазоны (
k
кk+1
,2k+1
к2k+1
,2k+1
к2k+3
, и2k+1
в2k+5
) не имеют никакого физического смысла. В любом случае, некоторые из них отображаются как промежуточные значения, потому что это проще, чем добавлять дополнительные проверки, чтобы избежать их.В левом стеке хранится количество правок, необходимых для преобразования каждой подстроки в сбалансированную строку. Расстояние редактирования для интервала
(x,y)
сохраняется на глубинеx + y(y-1)/2
.Во время внутреннего цикла записи добавляются над левым стеком, чтобы указать, какие перемещения возможны. Эти записи имеют длину 5 байт. Подсчет с вершины, номер
d+1
,y1
,x1
,y2
,x2
, где движение стоитd
редактировать шаги и водоразделы подстроку в(x1,y1)
и(x2,y2)
.Код
Описание приехать. На данный момент вот моя рабочая копия кода. Некоторые комментарии могут не соответствовать терминологии.
источник
Haskell , 797 байт
Попробуйте онлайн!
источник