Basic segmentation
Input
s = "leetcode", wordDict = ["leet", "code"]
Output
"leet code"
The string can be segmented into "leet" + "code"; return them joined by a space.
Full lesson preview
Solve word break with reconstruction
Determine if a string can be segmented into dictionary words and return one valid reconstruction.
Python practice25 minDynamic ProgrammingAdvancedLast updated March 29, 2026
Problem statement
Given a non-empty string s and a list of non-empty words wordDict, determine whether s can be segmented into a space-separated sequence of one or more dictionary words. If possible, return one valid reconstruction as a single string with words separated by single spaces. If there are multiple valid reconstructions you may return any one of them. If no reconstruction exists, return None (the test harness will treat None as an empty string). Use dynamic programming (memoization/tabulation) to achieve polynomial time.
Task
Implement a dynamic programming solution that decides if s can be segmented and reconstructs one valid segmentation (words separated by spaces).
Examples
Input format
A call to the function word_break_reconstruct(s, word_dict) where s is a string and word_dict is a list of strings.
Output format
Return a single string that is a valid segmentation (words joined by single spaces). If no segmentation exists return None (tests compare None as an empty string).
Constraints
- 0 <= len(s) <= 1000
- 1 <= len(word) for every word in wordDict
- wordDict size <= 1000
- All inputs are lowercase alphabetic strings for simplicity
- Aim for O(n^2) time with O(n) or O(n^2) space
Samples
Sample 1
Input
word_break_reconstruct("applepenapple", ["apple","pen"])
Output
"apple pen apple"
One valid segmentation is "apple pen apple".