O(1)

Method 4 - Top Down DP - DFS with memoization

In method 1, if the size of the dictionary is very large, the time is bad. Instead we can solve the problem in O(n^2) time (n is the length of the string).

For example, for string abcd the recursion tree will look like:

graph TD
	A["applepenapple"] -->|a| N1["pplepenapple ❌"]
	A -->|"..."| N2["❌"]
    A -->|apple| B["penapple"]
    A -->|...| C["❌"]
    
    B -->|p| D["enapple❌"]
    B -->|...| N3["❌"]
    B -->|pen| E["apple"]
    B -->|...| N4["❌"]
    
    E -->|a| N5["pple❌"]
    E -->|...| N6["❌"]
    E -->|apple| F["End of string → ✅"]

We can see that subproblems for “cd” is repeating twice. So, we can cache the solution.

Repetitive Subproblems

The recursive solution has many subproblems that are repeating at various stage of the recursion.

For instance, consider the case where s = "catsanddog" and wordDict = ["cat", "cats", "and", "sand", "dog"]. Suppose we are trying to break the string into words:

If we break it as "cat" followed by "sand", or as "cats" followed by "and", the remaining part of the string, "dog", is shared by both paths.
Since "dog" exists in the dictionary and can be successfully segmented, we should not need to recompute its result for both paths. Instead, we reuse the result (true), which saves us redundant calculations.

Code

Related Tags