Задачи
March 21

Задача. Разбивка строки

Задача: Дана строка 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].

Детали реализации смотрите ниже.

Реализация

Play-test

https://dotnetfiddle.net/e2g9tJ