During a recent job interview, I was asked to give a solution to the following problem:

Given a string s (without spaces) and a dictionary, return the words in the dictionary that compose the string.

For example, s= peachpie, dic= {peach, pie}, result={peach, pie}.

I will ask the the decision variation of this problem:

if s can be composed of words in the dictionary return yes, otherwise return no.

My solution to this was in backtracking (written in 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
}

What is the time complexity of this solution? I'm calling recursively in the for loop, but only for the prefix's that are in the dictionary.

Any idea's?