Back to Practice Dashboard
Top 150 InterviewMedium
Word Break
Learn how to solve the 'Word Break' problem. This detailed resource details brute force and optimized approaches.
Problem Statement
Medium
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.
Write a function wordBreak(s: str, wordDict: List[str]) -> bool.
Constraints
- •1 <= len(s) <= 300
- •1 <= len(wordDict) <= 1000
- •1 <= len(wordDict[i]) <= 20
- •s and wordDict[i] consist of only lowercase English letters
- •All the strings of wordDict are unique
Examples
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".
Example 3
Input
s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output
False
Explanation
No valid segmentation exists.
Need a Hint?
Define subproblem states, establish the recurrence relation, and use memoization (top-down) or tabulation (bottom-up).
Edge Cases to Watch
- Empty list or null input variables
- Single item lists/arrays
- Extremely large input bounds causing integer or stack overflow
Ready to Solve?
Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.