MEDIUM NC#108 Blind #20 Dynamic Programming 1D
139. Word Break
š Problem
Given a string s and a dictionary of strings wordDict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
š§ Visual Learning Aid
1 Model the input into the right structure
2 Choose the core technique and invariant
3 Execute step-by-step with a sample
4 Validate complexity and edge cases
JS/TS Refreshers
- ā¢Array methods (`push`, `pop`, `shift`, `slice`)
- ā¢Object/Map/Set usage patterns
- ā¢Function parameter and return typing
- ā¢Array DP table updates
- ā¢State transition thinking
- ā¢Base case initialization
Logical Thinking Concepts
- ā¢Define invariants before coding
- ā¢Check edge cases first (`[]`, single element, duplicates)
- ā¢Estimate time/space before implementation
- ā¢Apply Dynamic Programming reasoning pattern
- ā¢Apply DFS reasoning pattern
- ā¢Apply Recursion reasoning pattern
š” Approach
- ā dp[i] = true if s[0:i] can be segmented
- ā For each position i, check all substrings ending at i
- ā dp[0] = true (empty string is valid)
- ā Time: O(nĀ² * m) where n = s.length, m = avg word length, Space: O(n)
š§ Prerequisites
š ļø Hints & Pitfalls
Hints
- ā¢dp[i] = true if s[0:i] can be segmented
- ā¢For each position i, check all substrings ending at i
- ā¢dp[0] = true (empty string is valid)
Common Pitfalls
- ā¢Time: O(nĀ² * m) where n = s.length, m = avg word length, Space: O(n)
š§Ŗ Test Cases
Hidden tests on submit: 1
Test Case 1
Not run Input:
wordBreak('leetcode', ['leet','code']); Expected:
true Test Case 2
Not run Input:
wordBreak('applepenapple', ['apple','pen']); Expected:
true Test Case 3
Not run Input:
wordBreak('catsandog', ['cats','dog','sand','and','cat']); Expected:
false š Code Editor
š¤ Output