Word Break

We need to check if the entire string can be built using dictionary words. Words can be reused.

Example: s = "leetcode", dict = ["leet", "code"]

• "leet" + "code" -> Valid
• Output: true

We define dp[i] as a boolean: Is prefix s[0...i-1] valid?

Recurrence:
dp[i] = true IF exists some j < i such that:

1. dp[j] is true (prefix ending at j is valid)
2. s[j...i] is in the dictionary.

Base Case: dp[0] = true (empty string).

Watch how we check possible split points j. If dp[j] is valid AND the substring from j to i is in the dict, then dp[i] becomes valid.

Click 'Randomize' to test different strings.