20 / 75
Medium
Word Break
#20dynamic-programmingstringtriememoization
Check if string can be segmented into dictionary words using DP.
Example:
Input:
s='leetcode', wordDict=['leet','code']Output:
true ('leet' + 'code')Common Mistakes:
- Not using HashSet for O(1) lookup, causing TLE
- Forgetting to set dp[0] = true (base case)
- Not breaking early when dp[i] becomes true
Notes:
Can also solve with Trie + DFS/BFS. Time O(n² * m) where m is avg word length, Space O(n + dict size).
💻
Java Solution Hidden
Enable “Show Full Solution” to view the code
Check if string can be segmented into dictionary words using DP.
Example:
Input:
s='leetcode', wordDict=['leet','code']Output:
true ('leet' + 'code')Common Mistakes:
- Not using HashSet for O(1) lookup, causing TLE
- Forgetting to set dp[0] = true (base case)
- Not breaking early when dp[i] becomes true
Notes:
Can also solve with Trie + DFS/BFS. Time O(n² * m) where m is avg word length, Space O(n + dict size).
20/75
Word Break