Анонс. Разбивка строки

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