Создать заданную строку из словарных статей

Во время недавнего собеседования меня попросили дать решение следующей проблемы:

Учитывая строку s (без пробелов) и словарь, вернуть слова в словарь, составляющий строку.

Например, s = peachpie, dic = {peach, pie}, result = {peach, pie} .

Я спрошу вариант решения этого проблема:

если s может состоять из слов в возврат словаря да , иначе return no .

Мое решение этой проблемы заключалось в отслеживании с возвратом (написано на Java)

public static boolean words(String s, Set<String> dictionary)
{
    if ("".equals(s))
        return true;

    for (int i=0; i <= s.length(); i++)
    {
        String pre = prefix(s,i); // returns s[0..i-1]
        String suf = suffix(s,i); // returns s[i..s.len]
        if (dictionary.contains(pre) && words(suf, dictionary))
            return true;
    }
    return false;
}

public static void main(String[] args) {
    Set<String> dic = new HashSet<String>();
    dic.add("peach");
    dic.add("pie");
    dic.add("1");

    System.out.println(words("peachpie1", dic)); // true
    System.out.println(words("peachpie2", dic)); // false
}

Какова временная сложность этого решения? Я вызываю рекурсивно в цикле for, но только для префиксов, которые есть в словаре.

Есть идеи?