The core loop from the optimized solution:

```
for i in range(1, n+1):
for j in range(i):
if dp[j] and s[j:i] in word_set:
dp[i] = True
break
```

The time complexity of this algorithm is O(n^2), where n is the length of the input string.

In the if-condition, we create a string s[j:i]. Does this add an additional O(n) complexity, bringing our total complexity to O(n^3)?

Additionally, on line 4, we create a set of words in word_dict. Should our total time be O(w + n^3)?

Course: Grokking Coding Interview Patterns in Python - Learn Interactively

Lesson: Solution: Word Break - Grokking Coding Interview Patterns in Python