def word_break(s, word_dict):
n = len(s)
dp = [False] * (n + 1)
dp[0] = True
for i in range(1, n + 1):
for word in word_dict:
wlen = len(word)
if wlen > i or not dp[i - wlen]:
continue
if s[i - wlen:i] == word:
dp[i] = True
break
return dp[n]Variables
n- length of the input string sm- number of words in the dictionary
Explanation
For each of the `n` positions we try every dictionary word (`m` of them), and the substring comparison is up to `n` characters - **O(n² · m)** time. The DP array holds `n + 1` booleans, **O(n)** space.