LeetCode 140 Word Break II - Example and Complexity Analysis

Trace s = "catsand", wordDict = ["cat","cats","and"].

solve(0):

• "cat" matches s[0:3]. solve(3) → ["and"] → result: ["cat and"]
• "cats" matches s[0:4]. solve(4) → ["and"]? No, s[4:7]="and" but s[4:]="and" works. → result: ["cats and"]

Wait, let's be precise. s = "catsand" (length 7).

• Position 0: "cat" → solve(3). "cats" → solve(4).
• Position 3: "and" matches → solve(6). But length is 7, so solve(7).
• Position 4: "and" matches s[4:7] → solve(7).
• Position 7: base case, return [""].

Results: ["cat and", "cats and"].

Worst case $O(2^n)$ sentences (exponential). Space: $O(n \cdot 2^n)$ for all outputs.