What is the brute force approach and complexity for Word Break II?

Try every dictionary word at each position and recurse on the rest, with no memo with time complexity O(N² · 2^N) and space complexity O(N).

What is the optimal approach and complexity for Word Break II?

Store the sentences for each start index, so each suffix is solved once with optimal time complexity O(N³ + N · S) and space complexity O(N · S).

How do you identify the pattern for Word Break II?

Look for key signals in the prompt: "return all sentences" indicates Not a yes or no. The answer is a list of strings, so every valid route must be carried through.; "words from wordDict" indicates Each piece must match a dictionary word. A hash set checks a word in O(1) once its substring is built.; "a word can be reused" indicates The same start can match the same word again, so there is no used flag to undo..

Word Break II

Hard·LeetCode #140 Pro OnlySlight Variation

LeetCode

Problem Statement

You are given a string s and a list of words wordDict. Insert spaces into s so that every piece between spaces is a word from the list. A word can be used more than once. Return every sentence you can make this way. The sentences can be returned in any order.

Input

A string s, and wordDict, a list of distinct words.

Output

A list of every sentence that can be made from s, where a sentence is the words joined by single spaces. If there is none, return an empty list.

Example 1

Input: s = "catsanddog", wordDict = [cat, cats, and, sand, dog]

Output: [cats and dog, cat sand dog]

The first cut can be after cats, then and and dog follow. Or it can be after cat, then sand and dog follow.

Example 2

Input: s = "pineapplepenapple", wordDict = [apple, pen, applepen, pine, pineapple]

Output: [pine apple pen apple, pineapple pen apple, pine applepen apple]

The word apple is used twice in the first sentence. A word can be reused, so this is allowed.

Example 3

Input: s = "catsandog", wordDict = [cats, dog, sand, and, cat]

Output: []

Every route gets stuck. For example, cat and sand leave og, which is not a word.

Constraints

• 1 ≤ s.length ≤ 20
• 1 ≤ wordDict.length ≤ 1000
• 1 ≤ wordDict[i].length ≤ 10
• `s` and `wordDict[i]` consist of lowercase English letters.
• All the strings in `wordDict` are unique.
• The input is chosen so that the answer is at most 10^5 characters long.

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“return all sentences”

→ Not a yes or no. The answer is a list of strings, so every valid route must be carried through.

“words from wordDict”

→ Each piece must match a dictionary word. A hash set checks a word in O(1) once its substring is built.

“a word can be reused”

→ The same start can match the same word again, so there is no used flag to undo.

Approach Complexity Ladder

Brute Force — backtrack over every word, solving the rest each timeO(N² · 2^N)O(N)

Try every dictionary word at each position and recurse on the rest, with no memo

Optimal — memoize the sentences for each start indexO(N³ + N · S)O(N · S)

Store the sentences for each start index, so each suffix is solved once

Brute Force Intuition

From position start, try every word that matches s at start. Add it to the sentence and solve the rest from the next position. There is no memo, so the same suffix is solved again on every route that reaches it. When the position reaches the end of s, the sentence is complete.

Recognition rule for this sub-pattern:

Cut the string at every valid position and recurse on the rest.

Remember this · Backtracking

Trigger

"All subsets / permutations / combinations", place items under rules (N-Queens, Sudoku), find a path in a grid.

Think

At each step, what are my choices, and how do I undo a choice?

Key question

What is my state, when is it complete, and when do I prune?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Backtracking translate into production architectures and low-level memory mechanics.

LLD Architecture