The naive approach to solve this problem is to use a basic recursive strategy, which considers all possible prefixes of a string and checks if they are present in the dictionary. If a prefix is contained in the dictionary, the rest of the string is checked in the same manner. Time: O(2^n)
Say d is the number of words in our dictionary. Could our recursive branching factor in this case actually be O(d), because for a given substring of s, we could create O(d) possible branches? Could our time comp actually be O(d^n)?
Course: Grokking Coding Interview Patterns in Python - Learn Interactively
Lesson: Solution: Word Break - Grokking Coding Interview Patterns in Python