Решение задачи 2707. Extra Characters in a String
Дана строка s и словарь dictionary. Нужно разбить строку s на 1 или более неперересекающихся подстрок так, чтобы каждая подстрока присутствовала в словаре. При этом в строке s могут остаться символы, не входящие ни в одну из использованных подстрок. Задача - свести к минимуму количество таких символов, то есть разбить строку оптимально.
Ответ лежит в плоскости динамического программирования. Продвигаясь по строке посимвольно нам нужно решить - пропустить текущий символ (даже если он принадлежит подстроке, входящей в словарь) и увеличить на 1 счетчик неиспользованных символов, или же использовать подстроку с этим символом при разбиении и перейти к символу, следующему за последним символом использованной подстроки.
Для этого годится рекурсивный подход. Функция MinExtra(start) возвращает минимальное количество неиспользованных символов оставшихся после разбиения суффикса строки s начинающегося с позиции start (при 0 - индексации). Базовым случаем будет пустая подстрока - возвращаем 0. Нужно оценить два варианта:
- либо мы пропустим текущий символ и результатом будет
1 + MinExtra(start + 1). - либо попробуем использовать текущий символ при разбиении. В этом случае нужно проверить подстроки начинающиеся с текущей позиции на предмет наличия в словаре.
Есть два основных способа организации такой проверки:
- можно создать хеш-сет из словарных слов и последовательно проверять все возможные подстроки на предмет наличия их в словаре. Это даст квадратичную сложность от длины строки
s. - можно использовать структуру бор для хранения словаря. Тогда поиск можно будет прекратить после первого несовпадения подстроки со словарем. Бор позваляет создать дерево, переходы между узлами которого соответствуют символам словарных слов. Поиск слова представляет собой спуск по дереву. Максимальное количество переходов равно длине самого длинного словарного слова, что существенно уменьшает количество итераций при проверке подстроки на наличие в словаре.
Независимо от выбранного метода матчинга подстроки нам придется использовать специальный массив dp_ для сохранения результатов MinExtra() для уже рассчитанных позиций start, так как в процессе работы алгоритма возможны множественные рекурсивные вызовы MinExtra() для одинаковых позиций start. Массив dp_ длины равной длине строки s позволит избежать повторного расчета уже известных значений.
Мой код, приведенный в файле solution.cpp предлагает рекурсивное решение с мемоизацией (запоминанием расчитанных значений в массиве dp_). Для поиска по словарю я реализовал класс бора Trie.