Word Break

Asked byAmazonFacebookAppleQualtricsMicrosoftBloomberg

Problem

Given a string s and a dictionary of strings wordDict, determine whether s can be segmented into a sequence of one or more dictionary words, where words may be reused.

Examples

Example 1

Input:s = "leetcode", wordDict = ["leet","code"]

Output:true

Example 2

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

Output:false

Constraints

1 <= s.length <= 300

Solve it in the editor. Sign in free to run your Python or JavaScript against test cases, get a verdict, and track your attempts.

Solve on FeatCode →

How to approach it: the 1-D Dynamic Programming pattern

Break a problem into overlapping subproblems along a single dimension — like "the answer up to index i" — solve each one once, and reuse the result instead of recomputing it.

Look for this pattern when

A greedy or purely recursive approach recomputes the same subproblem repeatedly.
The problem asks for a count, a minimum/maximum, or a yes/no reachability over a sequence, where the answer at position `i` depends on answers at earlier positions.

Read the full 1-D Dynamic Programming guide →

Video walkthroughs

Original problem on LeetCode ↗