Задача. Разбивка строки
Задача: Дана строка S, а также словарь строк Dict. Необходимо определить можно ли разделить строку S на последовательность из одного или нескольких строк словаря.
Примечание: одна и та же строка словаря может использоваться несколько раз.
Входные данные: S - строка, ктр содержит только прописные буквы английского алфавита, Dict - список строк, все строки уникальны. Размер S - от 1 до 100, размер словаря от 1 до 1000.
1. S = "abcd", Dict = { "ab", "cd" }
Output: true
2. S = "abcde", Dict = { "ab", "bcd", "de" }
Output: false
Разбор
Разделяй и властвуй. Разделим исходную задачу на подзадачи, т.е. подстроки s1, s2. Если обе подзадачи удовлетворяют требуемым условиям, то и вся задача удовлетворяет тем же условиям. Таким образом, исходную строку мы разбиваем на меньшие подстроки и проверям их, используя заданный словарь.
Для реализации идеи используем метод динамического программирования.
Пусть dp - массив булевых значений размера Len + 1, где Len - длина исходной строки. Тогда dp[i] - указывает, можно ли разбить подстроку (0, i).
Очевидно, что dp[0] = true.
Далее запустим основной цикл по длине исходной строки, а в подцикле будем проверять можно ли разбить текущую подстроку. Выводом функции будет результат значения dp[Len].
Детали реализации смотрите ниже.