The Question
Coding

Word Break

Given a non-empty string s and a list of strings wordDict containing a dictionary of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words and each word can be reused multiple times in the segmentation. Example: Input: s = "leetcode", wordDict = ["leet", "code"] Output: true Explanation: Return true because "leetcode" can be segmented as "leet code". Constraints: - 1 <= s.length <= 300 - 1 <= wordDict.length <= 1000 - 1 <= wordDict[i].length <= 20 - s and wordDict[i] consist of only lowercase English letters.
Java
DP
HashSet
Questions & Insights

Clarifying Questions

Can dictionary words be reused? Yes, words in the wordDict can be used multiple times in the segmentation.
Is the comparison case-sensitive? Usually, yes, "Apple" and "apple" would be distinct unless specified.
What are the constraints on the length of the string and the size of the dictionary? This helps determine if an O(n^2) or O(n^3) approach is acceptable versus needing a Trie-based optimization.
What should be returned for an empty string? Typically, an empty string is segmentable if the logic treats it as a base case, but usually, the input s will have a minimum length of 1.
Assumptions:
The input string s consists of lowercase English letters.
The dictionary contains unique words.
1 \le s.length \le 300.
1 \le wordDict.length \le 1000.

Thinking Process

Identify Subproblems: To know if string S[0...i] is segmentable, we need to find some j < i such that S[0...j] is segmentable AND the substring S[j...i] exists in the dictionary.
Define State: Use a boolean array dp where dp[i] represents whether the prefix of length i.e., s.substring(0, i)) can be segmented into dictionary words.
State Transition: For each position i from 1 to n, check all previous positions j. If dp[j] is true and the substring from j to is in the wordDict, then dp[i] becomes true.
Optimization: Use a HashSet for the dictionary to achieve O(1) average time complexity for word lookups.
Implementation Breakdown

Problem Set

Functional Requirement: Return true if the input string can be segmented; otherwise, return false.
Constraint: The solution must handle strings up to 300 characters efficiently.
Boundary Condition: dp[0] must be initialized to true as the base case for the empty prefix.

Approach

Algorithm: Dynamic Programming (Bottom-Up).
Data Structure: HashSet for O(1) lookups, boolean[] for state tracking.
Complexity:
Time: O(n^2 \cdot k) where n is the length of the string and k is the average length of the substring operation (in Java, substring is O(k)).
Space: O(n + m) where n is the DP array and m is the space for the dictionary in the set.

Implementation

Wrap Up

Advanced Topics

Trie Optimization: If the dictionary is very large and the string is long, we can use a Trie to check valid substrings. Instead of checking all j < i, we can traverse the Trie using characters from s[i...n] to find valid words starting at i.
DFS with Memoization: This can be solved top-down. Memoization ensures that we don't re-calculate the same suffix multiple times, effectively yielding the same complexity as DP.
Space-Time Trade-off: If memory is tight, a recursive approach with a limited-depth cache might be preferred over a full DP table, though in this specific problem, O(n) space is generally negligible.