140. Word Break II
Word Break II (LeetCode 140) is a Hard 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.
How to solve Word Break II
Word Break II 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:
- Consider using dynamic programming to break down the problem into smaller subproblems related to substring segmentation.
- Think about how you can use a 1D DP array where each position represents whether the substring up to that index can form valid sentences.
- To generate all possible sentences instead of just a boolean answer, try to store not just true/false but the actual possible word combinations at each index.
The reference solution runs in O(2^n * n) time and O(2^n * n) space.
The Word Break II solution and editorial walks through the full approach with reference code.
Problem statement
Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.
Note that the same word in the dictionary may be reused multiple times in the segmentation.
Example 1:
Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"] Output: ["cats and dog","cat sand dog"]
Example 2:
Input: s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"] Output: ["pine apple pen apple","pineapple pen apple","pine applepen apple"] Explanation: Note that you are allowed to reuse a dictionary word.
Example 3:
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"] Output: []
Constraints:
- 1 <= s.length <= 20
- 1 <= wordDict.length <= 1000
- 1 <= wordDict[i].length <= 10
- s and wordDict[i] consist of only lowercase English letters.
- All the strings of wordDict are unique.
- Input is generated in a way that the length of the answer doesn't exceed 105.
Topics and companies
Topics: Array, Hash Table, String, Dynamic Programming, Backtracking, Trie, Memoization.
Reported in interviews at Facebook, Amazon, Bloomberg, ByteDance, Google, Microsoft.
How to practise Word Break II 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(2^n * n) time and O(2^n * n) space.
Open Word Break II in the code editor, or read the Word Break II editorial for a worked solution with its approach and complexity analysis.
Where Word Break II 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 II
Other problems that use the same 1D Array (Word Break Style) and Dynamic Programming (DP) Patterns techniques:
- Word Break — Medium, 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 II FAQ
What is the LeetCode number of Word Break II?
Word Break II is LeetCode problem 140, rated Hard.
What pattern is used to solve Word Break II?
Word Break II is a Word Break problem. It belongs to the Dynamic Programming (DP) Patterns pattern, in the 1D Array (Word Break Style) subpattern.
What is the time complexity of Word Break II?
The reference solution runs in O(2^n * n) time and O(2^n * n) space.
Which companies ask Word Break II?
Word Break II has been reported in interviews at Facebook, Amazon, Bloomberg, ByteDance, Google, Microsoft.