139. Word Break

Word Break (LeetCode 139) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Dynamic Programming (DP) Patterns pattern, in the 1D Array (Word Break Style) subpattern.

• Blind 75 · #57 of 75 · 1-D Dynamic Programming
• NeetCode 150 · #108 of 150 · 1-D Dynamic Programming
• NeetCode 250 · #184 of 250 · 1-D Dynamic Programming

How to solve Word Break

Word Break is a Word Break problem, part of Dynamic Programming (DP) Patterns. Determine if string can be segmented into dictionary words using DP.

Work towards the solution in these steps:

1. Consider if there is a way to build up the solution incrementally by checking smaller segments of the string before tackling the entire string.
2. Think about using a one-dimensional boolean array where each position indicates whether the substring up to that index can be segmented into dictionary words.
3. At each index, try to find if there is a previous index where the substring from that previous index to the current index forms a valid word and the substring before that previous index was also valid.

The reference solution runs in O(n * L) time and O(n + D) space.

The Word Break solution and editorial walks through the full approach with reference code.

Problem statement

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1:

Input: s = "leetcode", wordDict = ["leet","code"] Output: true Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple","pen"] Output: true Explanation: Return true because "applepenapple" can be segmented as "apple pen apple". Note that you are allowed to reuse a dictionary word.

Example 3:

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

Constraints:

- 1 <= s.length <= 300

- 1 <= wordDict.length <= 1000

- 1 <= wordDict[i].length <= 20

- s and wordDict[i] consist of only lowercase English letters.

- All the strings of wordDict are unique.

Topics and companies

Topics: Array, Hash Table, String, Dynamic Programming, Trie, Memoization.

Reported in interviews at Amazon, Apple, Bloomberg, ByteDance, eBay, Facebook, Google, Microsoft, Oracle, Qualtrics, Uber.

How to practise Word Break on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n * L) time and O(n + D) space.

Open Word Break in the code editor, or read the Word Break editorial for a worked solution with its approach and complexity analysis.

Where Word Break sits in the DSA pattern sheet

• Dynamic Programming (DP) Patterns pattern guide
• 1D Array (Word Break Style) subpattern
• The full DSA patterns sheet

Problems related to Word Break

Other problems that use the same 1D Array (Word Break Style) and Dynamic Programming (DP) Patterns techniques:

• Word Break II — Hard, same subpattern
• Best Time to Buy and Sell Stock — Easy, same pattern
• Best Time to Buy and Sell Stock II — Medium, same pattern
• Best Time to Buy and Sell Stock III — Hard, same pattern
• Best Time to Buy and Sell Stock IV — Hard, same pattern
• Best Time to Buy and Sell Stock with Cooldown — Medium, same pattern

Word Break FAQ